oj.uz

Submission #53627

# Submission time Handle Problem Language Result Execution time Memory
53627 2018-06-30T14:44:29 Z Diuven Salesman (IOI09_salesman) C++11
52 / 100
 1000 ms 34684 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=(1<<30), XMX=500001;
const ll linf=(1LL<<60);

int n, d, u, s;
struct shop {
    int t, x, a;
} S[MX];

inline ll _max(ll x, ll y){
    return x<y ? y : x;
}

struct Seg {
    static const int MX=(1<<20);
    ll tree[MX]; int n;
    void init(int sz){
        n=sz;
        for(int i=1; i<MX; i++) tree[i]=-linf;
    }
    void upt(int v, int s, int e, int pos, ll val){
        if(pos<s || e<pos) return;
        if(s==e){
            tree[v]=val;
            return;
        }
        upt(v*2,s,(s+e)/2,pos,val);
        upt(v*2+1,(s+e)/2+1,e,pos,val);
        tree[v]=_max(tree[v*2], tree[v*2+1]);
    }
    void upt(int pos, ll val){
        upt(1,1,n,pos,val);
    }
    ll mx(int v, int s, int e, int l, int r){
        if(r<s || e<l) return -linf;
        if(l<=s && e<=r) return tree[v];
        return _max(mx(v*2,s,(s+e)/2,l,r), mx(v*2+1,(s+e)/2+1,e,l,r));
    }
    ll mx(int l, int r){
        if(r<l) return -linf;
        return mx(1,1,n,l,r);
    }
} US, DS;


void upt(int pos, ll val){
    US.upt(pos, val+u*pos);
    DS.upt(pos, val-d*pos);
}

ll get(int x){
    ll upmx=US.mx(1,x)-u*x, dnmx=DS.mx(x,XMX)+d*x;
    return _max(upmx, dnmx);
}

ll T[MX];
ll X[MX], Y[MX];
void solve(int l, int r){
    for(int i=l; i<=r; i++)
        T[i]=get(S[i].x);
    X[l]=T[l]+S[l].a;
    for(int i=l+1; i<=r; i++)
        X[i]=_max(X[i-1]-d*(S[i].x-S[i-1].x), T[i])+S[i].a;
    // for(int i=r-1; i>=l; i--)
    //     X[i]=_max(X[i], X[i+1]-u*(S[i+1].x-S[i].x));
    
    Y[r]=T[r]+S[r].a;
    for(int i=r-1; i>=l; i--)
        Y[i]=_max(Y[i+1]-u*(S[i+1].x-S[i].x), T[i])+S[i].a;
    // for(int i=l+1; i<=r; i++)
    //     Y[i]=_max(Y[i-1]-d*(S[i].x-S[i-1].x), Y[i]);
    for(int i=l; i<=r; i++)
        upt(S[i].x, _max(X[i], Y[i]));
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>u>>d>>s;
    for(int i=1; i<=n; i++){
        int t,x,a;
        cin>>t>>x>>a;
        S[i]={t,x,a};
    }
    sort(S+1, S+n+1, [](shop &a, shop &b){
        if(a.t==b.t) return a.x<b.x;
        return a.t<b.t;
    });
    DS.init(500001);
    US.init(500001);
    upt(s, 0);
    int pos=1;
    while(pos<=n){
        int l=pos, r=pos;
        while(r<n && S[r+1].x==S[l].x) r++;
        solve(l,r);
        pos=r+1;
    }
    cout<<get(s);
    return 0;
}

Subtask #1
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16760 KB Output is correct
2 Correct 14 ms 16760 KB Output is correct
3 Correct 17 ms 16776 KB Output is correct
4 Correct 20 ms 16904 KB Output is correct
5 Correct 18 ms 17036 KB Output is correct
6 Correct 49 ms 17620 KB Output is correct
7 Correct 120 ms 18612 KB Output is correct
8 Correct 196 ms 20440 KB Output is correct
9 Correct 290 ms 22168 KB Output is correct
10 Correct 497 ms 27564 KB Output is correct
11 Correct 560 ms 27564 KB Output is correct
12 Correct 860 ms 31124 KB Output is correct
13 Correct 810 ms 31124 KB Output is correct
14 Correct 943 ms 34672 KB Output is correct
15 Correct 900 ms 34672 KB Output is correct
16 Execution timed out 1028 ms 34672 KB Time limit exceeded
17 Correct 17 ms 34672 KB Output is correct
18 Incorrect 14 ms 34672 KB Output isn't correct
19 Incorrect 15 ms 34672 KB Output isn't correct
20 Incorrect 17 ms 34672 KB Output isn't correct
21 Incorrect 18 ms 34672 KB Output isn't correct
22 Incorrect 19 ms 34672 KB Output isn't correct
23 Incorrect 18 ms 34672 KB Output isn't correct
24 Incorrect 20 ms 34672 KB Output isn't correct
25 Incorrect 177 ms 34672 KB Output isn't correct
26 Incorrect 331 ms 34672 KB Output isn't correct
27 Incorrect 578 ms 34672 KB Output isn't correct
28 Incorrect 595 ms 34672 KB Output isn't correct
29 Incorrect 780 ms 34672 KB Output isn't correct
30 Incorrect 804 ms 34684 KB Output isn't correct