gym 101047 problem F Fighting the Rajasi

Revision en2, by Los_Angelos_Laycurse, 2016-08-07 13:00:26

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...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Los_Angelos_Laycurse 2016-08-07 13:00:26 46 Tiny change: 'I have imp' -> 'http://codeforces.net/gym/101047/problem/F\n\nI have imp'
en1 English Los_Angelos_Laycurse 2016-08-07 12:59:47 819 Initial revision (published)