oj.uz

Submission #53612

# Submission time Handle Problem Language Result Execution time Memory
53612 2018-06-30T13:04:49 Z Diuven Salesman (IOI09_salesman) C++11
52 / 100
 1000 ms 22908 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=1e9, XMX=500001;

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

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

struct Seg {
    int tree[1100000], n;
    void init(int sz){
        n=sz;
        for(int i=1; i<1100000; i++) tree[i]=-inf;
    }
    void upt(int v, int s, int e, int pos, int 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, int val){
        upt(1,1,n,pos,val);
    }
    int mx(int v, int s, int e, int l, int r){
        if(r<s || e<l) return -inf;
        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));
    }
    int mx(int l, int r){
        if(r<l) return -inf;
        return mx(1,1,n,l,r);
    }
} US, DS;

int D[MX];

void upt(int pos, int val){
    D[pos]=val;
    US.upt(pos, val-u*(XMX-pos));
    DS.upt(pos, val-d*(pos));
}

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

int T[MX];
int 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), T[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);
    for(int i=1; i<=n; i++)
        upt(i,-inf);
    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 9 ms 8916 KB Output is correct
2 Correct 10 ms 8936 KB Output is correct
3 Correct 10 ms 9116 KB Output is correct
4 Correct 12 ms 9192 KB Output is correct
5 Correct 18 ms 9524 KB Output is correct
6 Correct 54 ms 11632 KB Output is correct
7 Correct 133 ms 12364 KB Output is correct
8 Correct 251 ms 13628 KB Output is correct
9 Correct 315 ms 14660 KB Output is correct
10 Correct 576 ms 18300 KB Output is correct
11 Correct 663 ms 18380 KB Output is correct
12 Correct 941 ms 20612 KB Output is correct
13 Correct 873 ms 20612 KB Output is correct
14 Execution timed out 1097 ms 22772 KB Time limit exceeded
15 Correct 831 ms 22884 KB Output is correct
16 Execution timed out 1085 ms 22884 KB Time limit exceeded
17 Correct 9 ms 22884 KB Output is correct
18 Incorrect 11 ms 22884 KB Output isn't correct
19 Incorrect 10 ms 22884 KB Output isn't correct
20 Incorrect 12 ms 22884 KB Output isn't correct
21 Incorrect 14 ms 22884 KB Output isn't correct
22 Incorrect 16 ms 22884 KB Output isn't correct
23 Incorrect 16 ms 22884 KB Output isn't correct
24 Incorrect 17 ms 22884 KB Output isn't correct
25 Incorrect 199 ms 22884 KB Output isn't correct
26 Incorrect 450 ms 22884 KB Output isn't correct
27 Incorrect 655 ms 22884 KB Output isn't correct
28 Incorrect 747 ms 22884 KB Output isn't correct
29 Execution timed out 1012 ms 22908 KB Time limit exceeded
30 Incorrect 943 ms 22908 KB Output isn't correct