Submission #1135045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135045		ByeWorld	Salesman (IOI09_salesman)	C++20	63 / 100	612 ms	40416 KiB

salesman

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 5e5+30;
const int SQRT = 610;
const int MAXA = 5e5+10;
const int MOD = 1e6+7;
const int INF = 2e9+10;
const int LOG = 21;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a,b); }

int n, u, d, s;

struct seg {
    int st[4*MAXN];
    void bd(int id, int l, int r){
        st[id] = -INF;
        if(l==r) return;
        bd(lf,l,md); bd(rg,md+1,r);
    }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return -INF;
        return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
    int upd(int id, int l,int r,int x,int p){
        if(l==r && l==x){
            chmx(st[id], p);
            return st[id];
        }
        if(r<x || x<l) return st[id];
        return st[id] = max(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p));
    }
} LE, RI;

int f[MAXN], f1[MAXN], f2[MAXN], val[MAXN];
vector <pii> vec;

void calc(int l, int r){
    for(int j=l; j<=r; j++){
        int p = vec[j].se;
        f1[p] = f2[p] = 
            max(LE.que(1,1,MAXA,1,p)-d*p, RI.que(1,1,MAXA,p,MAXA)+u*p);
    }
    f2[vec[l].se] += val[vec[l].se];
    f1[vec[r].se] += val[vec[r].se];

    for(int j=l+1; j<=r; j++)
        chmx(f2[vec[j].se], f2[vec[j-1].se]-d*(vec[j].se-vec[j-1].se)+val[vec[j].se]);
    for(int j=r-1; j>=l; j--)
        chmx(f1[vec[j].se], f1[vec[j+1].se]-u*(vec[j+1].se-vec[j].se)+val[vec[j].se]);
    
    for(int j=l; j<=r; j++){
        int p = vec[j].se;
        f[p] = max(f1[p], f2[p]); 
        LE.upd(1,1,MAXA,p,f[p]+d*p);
        RI.upd(1,1,MAXA,p,f[p]-u*p);
    
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> u >> d >> s;
    for(int i=1; i<=MAXA; i++) f[i] = -INF;
    LE.bd(1,1,MAXA); RI.bd(1,1,MAXA);
    f[s] = 0;

    LE.upd(1,1,MAXA,s,d*s); RI.upd(1,1,MAXA,s,-u*s); 

    for(int i=1; i<=n; i++){
        int d,id,w; cin>>d>>id>>w;
        val[id] = w;
        vec.pb({d, id});
    }
    vec.pb({MAXA, s});
    sort(vec.begin(), vec.end());

    for(int i=0; i<vec.size(); ){
        int xx = i;
        while(i<vec.size() && vec[i].fi == vec[xx].fi){ 
            i++;
        }
        calc(xx, i-1);

    }
    cout << f[s] << '\n';
}   

• Subtask 1: 63 / 100