oj.uz

Submission #906081

# Submission time Handle Problem Language Result Execution time Memory
906081 2024-01-13T13:30:15 Z ansol4328 Salesman (IOI09_salesman) C++14
100 / 100
 895 ms 52248 KB 
#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,-INF);
        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});
            L.updt(y,dp[y]+D*y);
        }
        for(auto& [y, z] : lst[i]) L.updt(y,pr[y]+D*y);

        reverse(lst[i].begin(),lst[i].end());
        for(auto& [y, z] : lst[i]){
            ll lv=-D*y+z+L.qry(1,y-1), rv=U*y+z+R.qry(y+1,E);
            pr[y]=max({pr[y], lv, rv});
            R.updt(y,pr[y]-U*y);
            dp[y]=max(dp[y],pr[y]);
        }
        for(auto& [y, z] : lst[i]) 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

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:64:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto& [y, z] : lst[i]) L.updt(y,pr[y]+D*y);
      |                   ^
salesman.cpp:67:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         for(auto& [y, z] : lst[i]){
      |                   ^
salesman.cpp:73:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         for(auto& [y, z] : lst[i]) L.updt(y,dp[y]+D*y), R.updt(y,dp[y]-U*y);
      |                   ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34136 KB Output is correct
2 Correct 48 ms 34140 KB Output is correct
3 Correct 49 ms 34136 KB Output is correct
4 Correct 51 ms 34292 KB Output is correct
5 Correct 53 ms 34392 KB Output is correct
6 Correct 79 ms 36888 KB Output is correct
7 Correct 123 ms 37828 KB Output is correct
8 Correct 196 ms 39572 KB Output is correct
9 Correct 273 ms 40960 KB Output is correct
10 Correct 459 ms 45844 KB Output is correct
11 Correct 550 ms 45652 KB Output is correct
12 Correct 700 ms 48960 KB Output is correct
13 Correct 668 ms 48964 KB Output is correct
14 Correct 863 ms 52032 KB Output is correct
15 Correct 741 ms 52248 KB Output is correct
16 Correct 895 ms 52096 KB Output is correct
17 Correct 50 ms 34224 KB Output is correct
18 Correct 49 ms 34232 KB Output is correct
19 Correct 55 ms 34140 KB Output is correct
20 Correct 54 ms 34140 KB Output is correct
21 Correct 51 ms 34136 KB Output is correct
22 Correct 55 ms 34348 KB Output is correct
23 Correct 54 ms 34388 KB Output is correct
24 Correct 53 ms 34140 KB Output is correct
25 Correct 167 ms 38484 KB Output is correct
26 Correct 285 ms 40556 KB Output is correct
27 Correct 487 ms 43260 KB Output is correct
28 Correct 428 ms 43760 KB Output is correct
29 Correct 609 ms 45468 KB Output is correct
30 Correct 595 ms 46492 KB Output is correct