There are N points cooridinate is x[1],x[2]....x[N];↵
try to partition these points into two sets {p1,p2,....pk1} (q1,q2,...qk2};p1<p2<..<pk1,q1<q2<..<qk2↵
the weight of partion w=abs(xp1)+abs(xp2-xp1)+abs(xp3-xp2)...+abs(xpk1-xp(k1-1)+abs(xq1)+abs(xq2-xq1)+...+abs(xqk2-xq(k2-1)).↵
↵
find the kth smallest partion..↵
N<=10000, K<=500000, x[i]<=100000000..↵
↵
you can submit this problem here:↵
↵
http://www.lydsy.com/JudgeOnline/problem.php?id=3945↵
↵
two partions are different if and only if the sets of them are different..↵
try to partition these points into two sets {p1,p2,....pk1} (q1,q2,...qk2};p1<p2<..<pk1,q1<q2<..<qk2↵
the weight of partion w=abs(xp1)+abs(xp2-xp1)+abs(xp3-xp2)...+abs(xpk1-xp(k1-1)+abs(xq1)+abs(xq2-xq1)+...+abs(xqk2-xq(k2-1)).↵
↵
find the kth smallest partion..↵
N<=10000, K<=500000, x[i]<=100000000..↵
↵
you can submit this problem here:↵
↵
http://www.lydsy.com/JudgeOnline/problem.php?id=3945↵
↵
two partions are different if and only if the sets of them are different..↵
