ZOJ 3699

浙大校内赛的题目，现场比赛的时候只有出两题，后面的模拟题都没时间做了。

题意：一辆汽车有个油箱，问他在经过n个加油站后能否到达目的地。每个加油站都有到下一加油站的距离和每升油的价格。

就是模拟过程，假设你是开车的你会怎么做，当然是尽量多的使用便宜的油。具体做法见代码：

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 100009;
#define LL long long
struct sta{
    LL x,y,vul;
}pos[Max];

struct oil {
    LL v,c;
};

oil sk[Max];

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        LL n,full;
        scanf("%lld%lld",&n,&full);
        for(int i = 0; i < n; i++) {
            scanf("%lld%lld%lld",&pos[i].x,&pos[i].y,&pos[i].vul);
        }
        
        LL ans = 0;
        int fro = 1,top = 0;
        LL now = 0;
        for(int i = 0; i < n; i++) {
            while(pos[i].vul < sk[top].c) {
                now -= sk[top].v;
                sk[top].v = 0;
                sk[top].c = 0;
                top--;
            }
            top++;
            sk[top].c = pos[i].vul;
            sk[top].v = full - now;
            now = full;
            LL need = pos[i].x * pos[i].y;
            if(need > full){
                ans = -1;
                break;
            }
            while(need > 0) {
                if(sk[fro].v < need) {
                    ans += sk[fro].c * sk[fro].v;
                    now -= sk[fro].v;
                    need -= sk[fro].v;
                    sk[fro].v = 0;
                    sk[fro].c = 0;
                    fro++;
                }
                else {
                    ans += sk[fro].c * need;
                    sk[fro].v -= need;
                    now -= need;
                    need = 0;
                }
            }
        }
        if(ans == -1)
            printf("Impossible\n");
        else
            printf("%lld\n",ans);
    }
    return 0;
}