Submission #768525

#	Time	Username	Problem	Language	Result	Execution time	Memory
768525		Dan4Life	Salesman (IOI09_salesman)	C++17	40 / 100	686 ms	64124 KiB

salesman

#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)); n = sz(a);
    for(int j : {0,1}) segTree[j].init(mxN); fill(dp+1,dp+mxN,-LINF);
    for(int i = 0; i < n; i++){
        int j = i; auto [t,l,m] = a[i];
        while(i<n and a[i][0]==a[i+1][0]) i++;
        if(i==j){
            dp[i] = max(dp[i], segTree[0].query(l+1,mxN)+l*u);
            dp[i] = max(dp[i], -l*d+segTree[1].query(1,l-1));
            dp[i]+=m; segTree[1].upd(l,dp[i]+l*d), segTree[0].upd(l,dp[i]-l*u);
        }
        else{
            int cur = -LINF;
            cur = max(cur, segTree[0].query(l,mxN)+l*u);
            cur = max(cur, -l*d+segTree[j].query(1,l));
            for(int k = j; k<=i; k++){
                auto [t,l,m] = a[k];
                cur+=m; segTree[1].upd(l,cur+l*d), segTree[0].upd(l,cur-l*u);
            }
            cur=-LINF;
            cur = max(cur, segTree[0].query(l+1,mxN)+l*u);
            cur = max(cur, -l*d+segTree[j].query(1,l-1));
            for(int k = i; k>=j; k--){
                auto [t,l,m] = a[k];
                cur+=m; segTree[1].upd(l,cur+l*d), segTree[0].upd(l,cur-l*u);
            }
        }
        
    }
    cout << dp[n-1];
}

Compilation message (stderr)

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: 40 / 100