Los_Angelos_Laycurse's blog

By Los_Angelos_Laycurse, history, 8 years ago, In English

http://codeforces.net/gym/101047/problem/F

I have implement an O(N^2) greedy algorithm and get Accepted, but I dont clear if it is correct:

first to fighting with all y-x>=0 from smallest x to biggest x, and throw out all y-x>=0 point

then sort remain point by increasing of (x-y). then check ,add every point to stk_list[] one by one. for each point i, choose the position of this point we will insert,the value

min(H-x1+y1-x2+y2-....-xj) for each j>=1&&j<=i after we insert point i must be biggest

if the maximum min(H-x1+y1-x2+y2-....-xj)<=0 then throw out this point and k--.

if we use binary_search approach and something like treap data structure, then total complexity is O(N*log(c)*log(n))

I have got accpeted, but I havenot prove its correctness and I don't know if test data is strong...

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting story m8.

I mean, if u want to ask u use question mark, thats how englando works