#2251. 盒子
盒子
盒子
题目描述
标题: 盒子 - Problem - QOJ.ac
The problem was used in the following contests:
sk 有 N 个漂亮的盒子,编号为 1∼N。第 i 个盒子有两个属性 Si 和 Pi,分别代表该盒子的大小和美丽程度。盒子 i 能够被放入所有满足 Si≤Sj 的盒子 j 中。
mxr 的生日要来了,于是 sk 打算给 mxr 送一些盒子作为生日礼物。因为送空盒子听起来不是很好,所以 sk 打算在盒子里面装其他盒子。具体地,sk 打算选择 K 对盒子,然后对每一对盒子,将某个盒子放到另一个里面(如果两个盒子的大小相同,他可以选择将哪个盒子放入另一个,否则他将小的那个盒子放入大的盒子中)。对每一对盒子 (i,j),如果盒子 i 在盒子 j 中,那么这一对盒子的美丽值为 Pj−Pi,因为 sk 觉得里面的盒子的美丽程度被浪费了。
由于拆盒子是一件很无聊的事,所以 mxr 可能不想要太多对盒子,并且 sk 不知道最理想的 K 值是多少。所以,对 1 到 ⌊n2⌋ 之间的每个 K,你需要帮 sk 找到他能用最多 K 对盒子得到的最高的总美丽值(即所有盒子对的美丽值之和的最大值)。
输入格式
第一行一个整数表示 N。
接下来 N 行每行两个整数表示 Si,Pi。
输出格式
输出 ⌊n2⌋行,第 i 行表示 k=i 时的答案。
样例一
input
5
1 4
1 5
1 3
3 4
3 1
output
3
5
限制与约定
对于 10% 的数据,N≤10。
对于 30% 的数据,N≤100。
对于 60% 的数据,N≤2×103。
对于 100% 的数据,1≤N≤2×105,1≤Si≤n,1≤Pi≤109。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5
1 4
1 5
1 3
3 4
3 1
3
5