记录编号	561283	评测结果	AAAAAAAAAA
题目名称	3097.[POJ 1456]超市	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2021-07-01 14:15:52	内存使用	2.13 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int d[maxn],p[maxn],n,pre[maxn];
int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
} 
void union_set(int r1,int r2) {
	pre[r2] = r1;
	return ;
}
int rk[maxn];
bool cmp(int a,int b) {
	return p[a] > p[b];
}
void work(void) {
	int D = 0;
	for(int i = 1;i <= n;++ i) {
		scanf("%d%d",&p[i],&d[i]);
		D = max(D , d[i]);
		rk[i] = i;
	}
	for(int i = 1;i <= D;++ i) {
		pre[i] = i;
	}
	int ans = 0;
	sort(rk + 1 , rk + 1 + n , cmp);
	for(int i = 1;i <= n;++ i) {
		int r = find(d[rk[i]]);
		if(r > 0) {
			ans += p[rk[i]];
			union_set(r - 1 , r);
		}
	}
	printf("%d\n",ans);
	return ;
}
int main() {
	freopen("supermarket.in","r",stdin);
	freopen("supermarket.out","w",stdout);
	while(~ scanf("%d",&n)) {
		work();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}