Submission #53511

# Submission time Handle Problem Language Result Execution time Memory
53511 2018-06-30T06:45:04 Z 노영훈(#1418) Salesman (IOI09_salesman) C++11
50 / 100
1000 ms 24200 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=1e9, XMX=5000001;

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

struct Seg {
    int tree[MX*4], n;
    void init(int sz){
        n=sz;
        for(int i=1; i<4*n; 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 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){
        return a.t<b.t;
    });
    DS.init(500001);
    US.init(500001);
    for(int i=1; i<=n; i++)
        upt(i,-inf);
    upt(s, 0);
    for(int i=1; i<=n; i++){
        int now=get(S[i].x);
        upt(S[i].x, now+S[i].a);
    }
    cout<<get(s);
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 15 ms 15996 KB Output is correct
2 Correct 15 ms 15996 KB Output is correct
3 Correct 18 ms 16284 KB Output is correct
4 Correct 19 ms 16284 KB Output is correct
5 Correct 21 ms 16384 KB Output is correct
6 Correct 54 ms 18432 KB Output is correct
7 Correct 119 ms 18756 KB Output is correct
8 Correct 254 ms 19488 KB Output is correct
9 Correct 307 ms 19900 KB Output is correct
10 Correct 638 ms 21868 KB Output is correct
11 Correct 679 ms 21868 KB Output is correct
12 Correct 965 ms 22988 KB Output is correct
13 Correct 804 ms 23012 KB Output is correct
14 Correct 948 ms 24028 KB Output is correct
15 Correct 783 ms 24164 KB Output is correct
16 Execution timed out 1093 ms 24200 KB Time limit exceeded
17 Incorrect 14 ms 24200 KB Output isn't correct
18 Incorrect 14 ms 24200 KB Output isn't correct
19 Incorrect 16 ms 24200 KB Output isn't correct
20 Incorrect 17 ms 24200 KB Output isn't correct
21 Incorrect 17 ms 24200 KB Output isn't correct
22 Incorrect 19 ms 24200 KB Output isn't correct
23 Incorrect 21 ms 24200 KB Output isn't correct
24 Incorrect 20 ms 24200 KB Output isn't correct
25 Incorrect 192 ms 24200 KB Output isn't correct
26 Incorrect 367 ms 24200 KB Output isn't correct
27 Incorrect 663 ms 24200 KB Output isn't correct
28 Incorrect 659 ms 24200 KB Output isn't correct
29 Execution timed out 1028 ms 24200 KB Time limit exceeded
30 Execution timed out 1008 ms 24200 KB Time limit exceeded