Discussion @ 1078. Segments @ Timus Online Judge

got AC in 0.31 but i still did n^2 is there anyhting better?

Posted by marius dumitran 15 Apr 2004 19:03

i used a df after i made an oriented graf(it's much easier to do than other solutions)
if u did it better than O(N*N)
please email me at dmarius1@yahoo.com
Thanks

Edited by author 15.04.2004 19:05

AC time 0.015, but O(N*N).

Posted by Vlad Veselov 16 Apr 2004 16:25

AC time 0.218, but N^3 and 884 kb memory

Posted by I am get tester... 31 Jul 2005 23:00

My decision not worse at all...

Re: AC time 0.218, but N^3 and 884 kb memory

Posted by Ayhan Aliyev [BOTL] 7 Feb 2006 19:59

At last! AC 0.001 and 394 KB

ac 0.001s O(n)

Posted by format_jam 20 Jan 2007 21:21

I use dp O(n).ac in 0.0001s
first,sort;
second dp: answer=max{f(1)..f(n)};
f(i) means the best sum from the i one

Re: ac 0.001s O(n)

Posted by elmariachi1414 (TNU) 15 Mar 2007 17:15

If you use sorting, it must be at least O(n*logn)

Re: got AC in 0.31 but i still did n^2 is there anyhting better?

Posted by A.06 8 Apr 2013 16:38

I used sorting and then found the LIS in O(nlogn) time, 0.031 seconds

Discussion of Problem 1078. Segments