oj.uz

Submission #768511

# Submission time Handle Problem Language Result Execution time Memory
768511 2023-06-28T08:20:21 Z Dan4Life Salesman (IOI09_salesman) C++17
62 / 100
 652 ms 40604 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)5e5+10;
const int LINF = (int)1e18;
int dp[mxN];
vector<array<int,3>> a;

struct SegTree{
    int seg[mxN*2];
    void init(int n){ fill(seg,seg+n*2,-LINF); }
    void upd(int x, int v, int p=0, int l=1, int r=mxN){
        if(l==r){ seg[p]=max(seg[p],v); return; }
        int mid = (l+r)/2; int rp = p+2*(mid-l+1);
        if(x<=mid) upd(x,v,p+1,l,mid);
        else upd(x,v,rp,mid+1,r);
        seg[p] = max(seg[p+1],seg[rp]);
    }
    int query(int i, int j, int p=0, int l=1, int r=mxN){
        if(i>r or j<l or i>j) return -LINF;
        if(i<=l and r<=j) return seg[p];
        int mid = (l+r)/2; int rp = p+2*(mid-l+1);
        return max(query(i,j,p+1,l,mid),query(i,j,rp,mid+1,r));
    }
} segTree[2];

int32_t main() {
    int n,u,d,s,t,l,m;
    cin >> n >> u >> d >> s;
    for(int i = 0; i < n; i++)
        cin >> t >> l >> m, a.pb({t,l,m});
    a.pb({0,s,0}); a.pb({mxN,s,0}); sort(all(a));
    for(int j : {0,1}) segTree[j].init(mxN); fill(dp+1,dp+mxN,-LINF);
    for(int i = 0; i <= n+1; i++){
        auto [t,l,m] = a[i];
        dp[i] = max(dp[i], segTree[0].query(l,mxN)+l*u);
        dp[i] = max(dp[i], -l*d+segTree[1].query(1,l));
        dp[i]+=m; segTree[1].upd(l,dp[i]+l*d), segTree[0].upd(l,dp[i]-l*u);
    }
    cout << dp[n+1];
}

Compilation message

salesman.cpp: In function 'int32_t main()':
salesman.cpp:36:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |     for(int j : {0,1}) segTree[j].init(mxN); fill(dp+1,dp+mxN,-LINF);
      |     ^~~
salesman.cpp:36:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   36 |     for(int j : {0,1}) segTree[j].init(mxN); fill(dp+1,dp+mxN,-LINF);
      |                                              ^~~~

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 8 ms 19792 KB Output is correct
3 Correct 8 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 13 ms 20136 KB Output is correct
6 Correct 32 ms 20804 KB Output is correct
7 Correct 69 ms 21936 KB Output is correct
8 Correct 138 ms 24108 KB Output is correct
9 Correct 193 ms 25808 KB Output is correct
10 Correct 382 ms 31680 KB Output is correct
11 Correct 384 ms 32320 KB Output is correct
12 Correct 469 ms 35420 KB Output is correct
13 Correct 537 ms 35696 KB Output is correct
14 Correct 652 ms 40604 KB Output is correct
15 Correct 588 ms 39772 KB Output is correct
16 Correct 591 ms 39784 KB Output is correct
17 Correct 7 ms 19796 KB Output is correct
18 Incorrect 8 ms 19868 KB Output isn't correct
19 Incorrect 10 ms 19928 KB Output isn't correct
20 Incorrect 10 ms 19984 KB Output isn't correct
21 Incorrect 9 ms 20052 KB Output isn't correct
22 Incorrect 13 ms 20180 KB Output isn't correct
23 Incorrect 12 ms 20116 KB Output isn't correct
24 Incorrect 13 ms 20116 KB Output isn't correct
25 Incorrect 119 ms 23720 KB Output isn't correct
26 Incorrect 236 ms 27436 KB Output isn't correct
27 Incorrect 377 ms 32720 KB Output isn't correct
28 Incorrect 420 ms 33568 KB Output isn't correct
29 Incorrect 556 ms 38184 KB Output isn't correct
30 Incorrect 594 ms 39096 KB Output isn't correct