oj.uz

답안 #905977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905977 2024-01-13T08:19:40 Z ansol4328 Salesman (IOI09_salesman) C++14
62 / 100
 809 ms 61048 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});
        }
        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;
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 34220 KB Output is correct
2 Correct 51 ms 34140 KB Output is correct
3 Correct 50 ms 34140 KB Output is correct
4 Correct 51 ms 34140 KB Output is correct
5 Correct 53 ms 34440 KB Output is correct
6 Correct 72 ms 37204 KB Output is correct
7 Correct 122 ms 38740 KB Output is correct
8 Correct 202 ms 41464 KB Output is correct
9 Correct 239 ms 43300 KB Output is correct
10 Correct 421 ms 50772 KB Output is correct
11 Correct 525 ms 51204 KB Output is correct
12 Correct 592 ms 54868 KB Output is correct
13 Correct 623 ms 55368 KB Output is correct
14 Correct 794 ms 61048 KB Output is correct
15 Correct 724 ms 60140 KB Output is correct
16 Correct 809 ms 60160 KB Output is correct
17 Correct 49 ms 34224 KB Output is correct
18 Incorrect 50 ms 34196 KB Output isn't correct
19 Incorrect 51 ms 34268 KB Output isn't correct
20 Incorrect 60 ms 34388 KB Output isn't correct
21 Incorrect 66 ms 34300 KB Output isn't correct
22 Incorrect 64 ms 34408 KB Output isn't correct
23 Incorrect 55 ms 34428 KB Output isn't correct
24 Incorrect 63 ms 34320 KB Output isn't correct
25 Incorrect 204 ms 39764 KB Output isn't correct
26 Incorrect 259 ms 43332 KB Output isn't correct
27 Incorrect 478 ms 47660 KB Output isn't correct
28 Incorrect 442 ms 49108 KB Output isn't correct
29 Incorrect 652 ms 52192 KB Output isn't correct
30 Incorrect 678 ms 53708 KB Output isn't correct