oj.uz

Submission #906073

# Submission time Handle Problem Language Result Execution time Memory
906073 2024-01-13T13:24:02 Z ansol4328 Salesman (IOI09_salesman) C++14
62 / 100
 791 ms 52096 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){
        i+=base;
        if(mx[i]>v) return;
        mx[i]=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);
        }
        reverse(lst[i].begin(),lst[i].end());
        for(auto& [y, z] : lst[i]){
            pr[y]=max(pr[y], U*y+z+R.qry(y+1,E));
            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:60:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for(auto& [y, z] : lst[i]){
      |                   ^
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:72:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         for(auto& [y, z] : lst[i]) L.updt(y,dp[y]+D*y), R.updt(y,dp[y]-U*y);
      |                   ^

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34208 KB Output is correct
2 Correct 49 ms 34136 KB Output is correct
3 Correct 53 ms 34248 KB Output is correct
4 Correct 61 ms 34140 KB Output is correct
5 Correct 55 ms 34412 KB Output is correct
6 Correct 84 ms 36888 KB Output is correct
7 Correct 128 ms 37812 KB Output is correct
8 Correct 209 ms 39508 KB Output is correct
9 Correct 292 ms 40960 KB Output is correct
10 Correct 419 ms 45620 KB Output is correct
11 Correct 554 ms 45836 KB Output is correct
12 Correct 675 ms 48968 KB Output is correct
13 Correct 709 ms 48960 KB Output is correct
14 Correct 738 ms 52092 KB Output is correct
15 Correct 757 ms 52096 KB Output is correct
16 Correct 791 ms 51912 KB Output is correct
17 Correct 62 ms 34140 KB Output is correct
18 Incorrect 53 ms 34252 KB Output isn't correct
19 Incorrect 50 ms 34252 KB Output isn't correct
20 Incorrect 58 ms 34396 KB Output isn't correct
21 Incorrect 51 ms 34276 KB Output isn't correct
22 Incorrect 53 ms 34136 KB Output isn't correct
23 Incorrect 64 ms 34388 KB Output isn't correct
24 Incorrect 61 ms 34356 KB Output isn't correct
25 Incorrect 181 ms 38564 KB Output isn't correct
26 Incorrect 220 ms 40384 KB Output isn't correct
27 Incorrect 420 ms 43260 KB Output isn't correct
28 Incorrect 381 ms 43764 KB Output isn't correct
29 Incorrect 595 ms 45632 KB Output isn't correct
30 Incorrect 484 ms 46272 KB Output isn't correct