제출 #905977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
905977		ansol4328	Salesman (IOI09_salesman)	C++14	62 / 100	809 ms	61048 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});
        }
        for(auto& [y, z] : lst[i]){
            if(pr[y]!=dp[y]) L.updt(y,dp[y]+D*y), R.updt(y,dp[y]-U*y);
            pr[y]=dp[y];
            dp[y]=max(dp[y], -D*y+z+L.qry(1,y-1));
            if(dp[y]!=pr[y]) L.updt(y,dp[y]+D*y);
        }
        reverse(lst[i].begin(),lst[i].end());
        for(auto& [y, z] : lst[i]){
            pr[y]=dp[y];
            dp[y]=max(dp[y], U*y+z+R.qry(y+1,E));
            if(dp[y]!=pr[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;
}

컴파일 시 표준 에러 (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]){
      |                   ^
salesman.cpp:63:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         for(auto& [y, z] : lst[i]){
      |                   ^
salesman.cpp:70:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |         for(auto& [y, z] : lst[i]){
      |                   ^

• Subtask 1: 62 / 100