Bucharest, Romania 2013 A Russian Dolls 贪心

 1 // File Name: 12895.cpp
 2 // Author: darkdream
 3 // Created Time: 2014年08月16日 星期六 23时41分13秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 
26 using namespace std;
27 struct node{
28     int x, y , c,ok;
29 }a[1005];
30 int cmp(node a, node b)
31 {
32     return a.c > b.c ; 
33 }
34 int main(){
35     int n ; 
36     while(scanf("%d",&n)!= EOF)
37     {
38         memset(a,0,sizeof(a));
39         for(int i = 1;i <= n;i ++)
40         {
41             scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c) ;
42             a[i].ok = 1;
43         }
44         sort(a+1,a+1+n,cmp);
45         LL ans = 0 ; 
46         for(int i = 1;i <= n;i ++)
47         {
48             int site = 0 ; 
49             int mx = 0;
50             for(int j = 1;j <= n;j ++)
51             {
52                 if(a[j].ok && a[i].y  >  a[j].x )
53                 {
54                     if(a[j].x > mx)
55                     {
56                         mx = a[j].x;
57                         site = j ; 
58                     }
59                 }
60             }
61             if(site)
62             {
63                 a[site].ok = 0 ;
64             }
65             ans += (a[i].y - mx)*a[i].c ; 
66         }
67         printf("%I64d\n",ans);
68     }        
69     return 0;
70 }