题目

全WA求调

//#pragma GCC optimize(2,3,"Ofast","inline")

#include <bits/stdc++.h>

//#define int long long
//#define double long double
#define ll long long
#define pii pair<int,int> 
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(s) ((int)s.size())
#define lowbit(x) (x&-x)
#define endl "\n"
//#define cout cout << "Output: "

using namespace std;

void inline solve(int C);

signed main(){
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(time(0));
    #ifndef ONLINE_JUDGE
        //system("cls");
        //freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
    #endif
    int T=1,C=0;
    //cin >> C;
    //cin >> T;
    while(T--) solve(C);
    return 0;
}

const int N=3e5+10;

int n,s,q[N],tl,dp[N],sc[N],st[N],x[N],y[N];

void inline solve(int C){
    cin >> n >> s;
    for(int i=1;i<=n;i++){
        cin >> st[i] >> sc[i];
        st[i]+=st[i-1],sc[i]+=sc[i-1];
    }
    q[++tl]=0;
    for(int i=1;i<=n;i++){
        int k=-st[i]-s;
        int l=1,r=tl;
        while(l<r){
            int mid=(l+r)/2;
            if(k*(x[q[mid]]-x[q[mid+1]])<y[q[mid+1]]-y[q[mid]]){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        int j=q[r];
        dp[i]=k*x[j]+y[j]+sc[n]*(st[i]+s);
        x[i]=sc[i],y[i]=(sc[i]-sc[n])*st[i]+dp[i];
        while(tl>1 && (y[q[tl-1]]-y[i])*(x[q[tl]]-x[q[tl-1]])>(y[q[tl-1]]-y[q[tl]])*(x[i]-x[q[tl-1]])){
            tl--;
        }
        q[++tl]=i;
    }
    cout << dp[n] << endl;
}