oj.uz

Submission #906013

# Submission time Handle Problem Language Result Execution time Memory
906013 2024-01-13T09:28:54 Z ansol4328 Salesman (IOI09_salesman) C++14
62 / 100
 759 ms 52088 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);
        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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 34136 KB Output is correct
2 Correct 49 ms 34140 KB Output is correct
3 Correct 48 ms 34232 KB Output is correct
4 Correct 49 ms 34140 KB Output is correct
5 Correct 52 ms 34384 KB Output is correct
6 Correct 74 ms 36944 KB Output is correct
7 Correct 122 ms 37968 KB Output is correct
8 Correct 191 ms 39568 KB Output is correct
9 Correct 254 ms 41136 KB Output is correct
10 Correct 411 ms 45904 KB Output is correct
11 Correct 411 ms 45912 KB Output is correct
12 Correct 538 ms 48980 KB Output is correct
13 Correct 475 ms 48964 KB Output is correct
14 Correct 759 ms 51920 KB Output is correct
15 Correct 693 ms 52088 KB Output is correct
16 Correct 733 ms 52080 KB Output is correct
17 Correct 53 ms 34140 KB Output is correct
18 Incorrect 50 ms 34140 KB Output isn't correct
19 Incorrect 52 ms 34136 KB Output isn't correct
20 Incorrect 58 ms 34312 KB Output isn't correct
21 Incorrect 50 ms 34276 KB Output isn't correct
22 Incorrect 52 ms 34140 KB Output isn't correct
23 Incorrect 55 ms 34388 KB Output isn't correct
24 Incorrect 57 ms 34140 KB Output isn't correct
25 Incorrect 141 ms 38564 KB Output isn't correct
26 Incorrect 205 ms 40524 KB Output isn't correct
27 Incorrect 300 ms 43132 KB Output isn't correct
28 Incorrect 329 ms 43608 KB Output isn't correct
29 Incorrect 432 ms 45632 KB Output isn't correct
30 Incorrect 446 ms 46548 KB Output isn't correct