公式解説の通りのインラインdpで\(\displaystyle\max_i\{\mathrm{dp}_i-C|x-i|\}\)をうまく管理して高速にこのdpを行うことを考えます。

定数\(c\)に対し、\(f(x)=a-c|x-b|\)の形をした関数を\(2\)つ取ったとき、\(|x-b|\)の係数が同じなので、この\(2\)つの関数は\(1\)つの交点を持つか、片方の関数が常にもう片方の関数以上の値をとるかの\(2\)通りの関係しかあり得ません。

したがって、\(\mathrm{dp}_i-C|x-i|\)が\(\max\)に寄与しうる\(i\)の集合を\(S\)として、ある\(t\)に対して\(\displaystyle\max_i\{\mathrm{dp}_i-C|t-i|\}\)を求めるとき、\(t\)以上の\(S\)の最小の要素と\(t\)未満の\(S\)の最大の要素をそれぞれ\(p,q\)として\(\max\{\mathrm{dp}_p-C|t-p|,\mathrm{dp}_q-C|t-q|\}\)を求めれば良いです。

\(S\)の管理は、ある\(i\)について\(\mathrm{dp}_i\)を更新したとき、\(S\)に含まれる\(i\)の前後の要素についてそれぞれ\(S\)から削除する必要がある間削除することを繰り返し、\(S\)に\(i\)を追加する必要があるなら追加するということを行えば良いです。

削除される回数が高々追加した回数であることに注意すると、std::setのようなデータ構造を用いて実装すれば時間計算量は\(O(M \log \min\{N,M\})\)で十分高速です。

提出(C++)

#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;
}