|
|
This is when there's only one pole. 1 1 2 The answer should be: 1 1 Try this test: 4 4 4 1 3 2 2 3 1 3 2 1 2 3 2 4 This sample correct? Edited by author 14.07.2010 13:02 yes, it is correct. for both of samples below answer is 1 (anyone of poles) 3 1 2 3 2 4 2 3 2 1 2 3 2 4 Any idea what is that test case ? I think there is inaccuracy in conditions. I answer the first example 2 5 1 3. Why is not it correct? Edited by author 02.03.2008 12:04 2 5 1 3 - is it correct. Edited by author 14.07.2008 22:50 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 |
|
|