Обсуждение @ 1078. Отрезки @ Timus Online Judge

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

Послано marius dumitran 15 апр 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).

Послано Vlad Veselov 16 апр 2004 16:25

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

Послано I am get tester... 31 июл 2005 23:00

My decision not worse at all...

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

Послано Ayhan Aliyev [BOTL] 7 фев 2006 19:59

At last! AC 0.001 and 394 KB

ac 0.001s O(n)

Послано format_jam 20 янв 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)

Послано elmariachi1414 (TNU) 15 мар 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?

Послано A.06 8 апр 2013 16:38

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

Обсуждение задачи 1078. Отрезки