Submission #1234522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234522		shjeong	Salesman (IOI09_salesman)	C++20	30 / 100	548 ms	82992 KiB

salesman

//U, D 반대임
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e9;
ll n;
struct segtree{
    vector<ll> tree;
    segtree(): tree(2020202,-Lnf){}
    void upd(ll node, ll s, ll e, ll i, ll d){
        if(s==e){ tree[node]=d; return; }
        ll mid = s+e>>1;
        if(i<=mid)upd(node<<1,s,mid,i,d); else upd(node<<1|1,mid+1,e,i,d);
        tree[node] = max(tree[node<<1],tree[node<<1|1]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(e<l or r<s)return -Lnf;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1; return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
} segU, segD;
ll D, U, S;
ll T[505050], L[505050], M[505050];
vector<ll> X[505050], P[505050];
ll dp[505050][2];
ll t;
//T : compressed
const ll MX = 500001;
int main(){
    fast;
    cin>>n>>D>>U>>S;
    vector<ll> cp = {0};
    for(int i = 1 ; i <= n ; i++){
        cin>>T[i]>>L[i]>>M[i];
        cp.push_back(T[i]);
    }
    L[0] = S;
    segU.upd(1,1,MX,S,dp[0][1] + L[0] * U);
    segD.upd(1,1,MX,S,dp[0][1] - L[0] * D);
    sort(all(cp)); COMP(cp);
    for(int i = 1 ; i <= n ; i++){
        T[i] = lower_bound(all(cp), T[i]) - cp.begin();
        X[T[i]].push_back(i);
    }
    t = sz(cp)-1;
    for(int i = 1 ; i <= t ; i++){
        sort(all(X[i]), [&](ll a, ll b){
            return L[a] < L[b];
        });
        ll s=0;
        for(auto j : X[i]){
            s += M[j];
            P[i].push_back(s);
        }
    }
    ll ans = 0;
    for(int ti = 1 ; ti <= t ; ti++){
        vector<ll> pre(sz(X[ti])+1), suf(sz(X[ti])+1);
        for(int i = 0 ; i < sz(X[ti]) ; i++){
            ll I = X[ti][i];
            dp[I][0] = max(segU.query(1,1,MX,1,L[I]) - L[I]*U, segD.query(1,1,MX,L[I],MX) + L[I]*D) + M[I];
            pre[i] = max((i==0?-Lnf:pre[i-1]),dp[I][0] + L[I]*U-P[ti][i]);
        }
        for(int i = sz(X[ti])-1 ; i >= 0 ; i--){
            ll I = X[ti][i];
            suf[i] = max((i==sz(X[ti])-1 ? -Lnf:suf[i+1]),dp[I][0] - L[I]*D + (i==0?0:P[ti][i-1]));
        }
        for(int i = 0 ; i < sz(X[ti]) ; i++){
            ll I = X[ti][i];
            dp[I][1] = max(pre[i] - L[I]*U + P[ti][i], suf[i] + L[I]*D + (i==0?0:P[ti][i-1]));
            segU.upd(1,1,MX,L[I],dp[I][1] + L[I] * U);
            segD.upd(1,1,MX,L[I],dp[I][1] - L[I] * D);
            ans = max(ans, dp[I][1] - (L[I]<S ? (S-L[I])*U : (L[I]-S)*D));
//            cout<<I<<" "<<dp[I][1]<<endl;
        }
    }
    cout<<ans;
}

• Subtask 1: 30 / 100