|
|
вернуться в форумI've got TLE at Test#10,so I want to know how many test cases there are.
If there are only near 10 cases,I'll improve on my program,or else,I'll give it up.
Who can help me? I suppose there are much more than 10 testcases. My solution works about 0.1 sec on any test, so timelimit is quite enough. Try to create quicker algo... Thank you.
I've found that greedy algorithm can solve this problem,thus no longer need dynamic progrmming.
And I've got AC. Can you tell me your greedy algorithm? Greedy? Please tell us your idea. I think that "greedy" here is terminologic mismatch.
Right termin is "simple constructive" algo.
Candidat to optimum easy to find simply tracing
trajectory of all points sorted by y- coordinate. Not mismatch at all. The simplest way to solve the problem is to find a greedy algo. I solved it with DP+date structure like "the stars" task.
0.578 sec, 44 896 КB...
How to solve it with greedy algo? Data structure i used is Binary Index Tree |
|
|
