Fuel Economy

思路

我们可以把终点看成距离为d，价格为0的加油站
每次到达加油站我们都要把油箱加满
如果每站之间距离大于油箱容量（第一站是否达到看当前容量），输出-1
假设油箱中的油有区别，并且可被替换
我们优先使用价格低的油，到下一个加油站时可以把当前油箱中比当前加油站的油贵的油替换成当前加油站的油
用双端队列维护模拟即可

代码

// Problem: Fuel Economy
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/24408
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=50005;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

struct node{
    ll x,y;
}p[N];

deque<node> q;//价格从小到大
ll ans,oil;

void solve(){
    int n;ll g,b,d;cin>>n>>g>>b>>d;
    rep(i,1,n) cin>>p[i].x>>p[i].y;
    sort(p+1,p+1+n,[](node a,node b){
        return a.x<b.x;
    });
    p[n+1]={d,0};
    q.push_back({b,0});
    oil=b;
    rep(i,0,n){
        ll dd=p[i+1].x-p[i].x;
        oil-=dd;
        if(oil<0) return cout<<"-1\n",void(0);
        while(dd){
            auto t=q.front();q.pop_front();
            ll tmp=min(dd,t.x);
            dd-=tmp;t.x-=tmp;
            if(t.x) q.push_front(t);
        }
        auto t=q.back();
        while(!q.empty()&&t.y>p[i+1].y){
            q.pop_back();
            oil-=t.x;
            ans-=t.x*t.y;
            t=q.back();
        }
        q.push_back({g-oil,p[i+1].y});
        ans+=(g-oil)*p[i+1].y;
        oil=g;
    }
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}