Submission #1134896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134896		ByeWorld	Salesman (IOI09_salesman)	C++20	60 / 100	534 ms	48180 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 = 1e18+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;
vector <ipii> vec;

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

int QUE(int id){
    return max(LE.que(1,1,MAXA,id,id) + id*u, 
        RI.que(1,1,MAXA,id,id) - id*d);
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> u >> d >> s;
    LE.bd(1,1,MAXA); RI.bd(1,1,MAXA);
    LE.upd(1,1,MAXA,1,s,-s*u); RI.upd(1,1,MAXA,s,MAXA,s*d); 

    // for(int i=1; i<=s-1; i++) dp[i] = -(s-i)*u; // -s*u + i*u
    // for(int i=s+1; i<=MAXA; i++) dp[i] = -(i-s)*d; // -i*d + s*d

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

    for(int i=0; i<vec.size(); ){
        int j = i;
        vector <pii> te;
        while(i<vec.size() && vec[i].fi == vec[j].fi) 
            te.pb({QUE(vec[i].se.fi)+vec[i].se.se, vec[i].se.fi}), i++;

        for(auto [nw, idx] : te){
            LE.upd(1,1,MAXA,1,idx, nw-idx*u);
                // nw - idx*u + i*u
            RI.upd(1,1,MAXA,idx,MAXA, nw+idx*d);
                // nw + idx*d - i*d
        }
    }
    // for(int i=0; i<vec.size(); ){
    //     int j = i;
    //     vector <pii> te;
    //     while(i<vec.size() && vec[i].fi == vec[j].fi) 
    //         te.pb({dp[vec[i].se.fi]+vec[i].se.se, vec[i].se.fi}), i++;

    //     for(auto [nw, idx] : te){
    //         for(int i=1; i<=idx; i++) chmx(dp[i], nw-(idx-i)*u);
    //             // nw - idx*u + i*u
    //         for(int i=idx+1; i<=MAXA; i++) chmx(dp[i], nw-(i-idx)*d);
    //             // nw + idx*d - i*d
    //     }
    // }
    
    cout << QUE(s) << '\n';
}   

• Subtask 1: 60 / 100