Submission #53450758

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1e18;
template<typename T>
bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,c,m;
    cin>>n>>c>>m;
    vector<ll> dp(n+1,-INF);
    dp[1]=0;
    struct func{
        ll a,b,d;
        ll get(ll x){
            return d-abs(x-b)*a;
        }
        bool operator<(const func& o) const{
            return b<o.b;
        }
    };
    set<func> trick;
    trick.insert(func{c,1,dp[1]});
    auto add=[&](func l)->void{
        bool DO=true;
        auto itr=trick.lower_bound(l);
        if(itr!=trick.end()){
            func cur=*itr;
            while(cur.d<=l.get(cur.b)){
                trick.erase(cur);
                itr=trick.lower_bound(l);
                if(itr==trick.end()) break;
                cur=*itr;
            }
            if(l.d<=cur.get(l.b)){
                DO=false;
            }
        }
        if(itr!=trick.begin()){
            itr--;
            func cur=*itr;
            while(cur.d<=l.get(cur.b)){
                trick.erase(cur);
                itr=trick.lower_bound(l);
                if(itr==trick.begin()) break;
                itr--;
                cur=*itr;
            }
            if(l.d<=cur.get(l.b)){
                DO=false;
            }
        }
        if(DO) trick.insert(l);
    };
    for(int i=0;i<m;i++){
        ll t,p;
        cin>>t>>p;
        ll tmp=-INF;
        func f=func{c,t,dp[t]};
        auto itr=trick.lower_bound(f);
        if(itr!=trick.end()){
            func cur=*itr;
            chmax(tmp,cur.get(t));
        }
        if(itr!=trick.begin()){
            itr--;
            func cur=*itr;
            chmax(tmp,cur.get(t));
        }
        tmp+=p;
        chmax(dp[t],tmp);
        add(func{c,t,dp[t]});
    }
    cout<<*max_element(dp.begin(),dp.end())<<endl;
}

Submission Info

Judge Result