zoj3699Dakar Rally

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100010
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 LL m[N],co[N],pr[N];
18 LL o[N];
19 int main()
20 {
21     int i,j,n,t,c;
22     cin>>t;
23     while(t--)
24     {
25         cin>>n>>c;
26         memset(o,0,sizeof(o));
27         priority_queue <LL> q;
28         priority_queue<LL, vector<LL>, greater<LL> > p;
29         for(i = 1 ; i <= n ;i++)
30         cin>>m[i]>>co[i]>>pr[i];
31         int flag = 1;
32         int ts = 0;
33         LL sum = 0;
34         for(i = 1; i <= n ;i++)
35         {
36             if(m[i]*co[i]>c){flag = 0;break;}
37             int s = 0;
38             while(!q.empty()&&pr[i]<=q.top())
39             {
40                 sum-=o[q.top()]*q.top();
41                 s+=o[q.top()];o[q.top()] = 0;q.pop();
42             }
43             o[pr[i]] = s+c-ts;
44             if(o[pr[i]])
45             {
46                 sum+=o[pr[i]]*pr[i];
47                 q.push(pr[i]);
48                 p.push(pr[i]);
49             }
50             LL ss = m[i]*co[i];
51             ts=c-ss;
52             while(ss)
53             {
54                 int k = p.top();
55                 if(o[k]<=ss)
56                 {
57                     ss-=o[k];o[k] = 0;
58                 }
59                 else
60                 {
61                     o[k]-=ss;ss = 0;
62                     break;
63                 }
64                 p.pop();
65             }
66         }
67         if(!flag)
68         {
69             puts("Impossible");
70             continue;
71         }
72         while(!q.empty())
73         {
74             int k = q.top();
75             sum-=o[q.top()]*q.top();
76             q.pop();
77         }
78         cout<<sum<<endl;
79     }
80     return 0;
81 }