gym 101047 problem F Fighting the Rajasi

Правка en1, от Los_Angelos_Laycurse, 2016-08-07 12:59:47

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Los_Angelos_Laycurse 2016-08-07 13:00:26 46 Tiny change: 'I have imp' -> 'http://mirror.codeforces.com/gym/101047/problem/F\n\nI have imp'
en1 Английский Los_Angelos_Laycurse 2016-08-07 12:59:47 819 Initial revision (published)