POJ 1456

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct type{
 5     int profit;
 6     int deadline;
 7 }prod[10000+5];
 8 bool day[10000+5];
 9 bool cmp(type x,type y)
10 {
11     return x.profit>y.profit;
12 }
13 int main()
14 {
15     int n;
16     while(scanf("%d",&n)!=EOF)
17     {
18         for(int i=1;i<=n;i++) scanf("%d %d",&prod[i].profit,&prod[i].deadline);
19         sort(prod+1,prod+n+1,cmp);
20         memset(day,0,sizeof(day));
21         int profit_sum=0;
22         for(int i=1;i<=n;i++){
23             for(int j=prod[i].deadline;j>=1;j--)
24             {
25                 if(day[j] == 0){
26                     day[j]=1;
27                     profit_sum+=prod[i].profit;
28                     break;
29                 }
30             } 
31         }
32         printf("%d
",profit_sum);
33     }
34 }