Submission #906013

#	Time	Username	Problem	Language	Result	Execution time	Memory
906013		ansol4328	Salesman (IOI09_salesman)	C++14	62 / 100	759 ms	52088 KiB

salesman

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1e18;
 
struct SegTree{
    vector<ll> mx;
    int base;
    SegTree(int a){
        base=1;
        while(base<a) base<<=1;
        mx.resize(base*2);
        base--;
    }
    void updt(int i, ll v){
        mx[i+=base]=v;
        for(i>>=1 ; i ; i>>=1) mx[i]=max(mx[i*2],mx[i*2+1]);
    }
    ll qry(int l, int r){
        ll ret=-INF;
        for(l+=base, r+=base ; l<=r ; l>>=1, r>>=1){
            if(l&1) ret=max(ret,mx[l++]);
            if(~r&1) ret=max(ret,mx[r--]);
        }
        return ret;
    }
};
 
ll N, U, D, S;
vector<P> lst[500005];
ll dp[500005], pr[500005];
const int E=500001;
 
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> N >> U >> D >> S;
    for(int i=1 ; i<=N ; i++){
        int x, y, z;
        cin >> x >> y >> z;
        lst[x].pb({y,z});
    }
 
    SegTree L(E), R(E);
    for(int i=1 ; i<=E ; i++){
        if(i<=S) dp[i]=-U*(S-i);
        else dp[i]=-D*(i-S);
        L.updt(i,dp[i]+D*i);
        R.updt(i,dp[i]-U*i);
    }
 
    for(int i=1 ; i<E ; i++){
        sort(lst[i].begin(),lst[i].end());
        for(auto& [y, z] : lst[i]){
            pr[y]=dp[y];
            ll lv=-D*y+z+L.qry(1,y-1), rv=U*y+z+R.qry(y+1,E);
            dp[y]=max({dp[y], lv, rv});
            if(dp[y]!=pr[y]) L.updt(y,dp[y]+D*y), R.updt(y,dp[y]-U*y);
        }
    }
 
    ll ans=0;
    for(int i=1 ; i<=E ; i++){
        if(i<=S) ans=max(ans,dp[i]-D*(S-i));
        else ans=max(ans,dp[i]-U*(i-S));
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:58:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for(auto& [y, z] : lst[i]){
      |                   ^

• Subtask 1: 62 / 100