oj.uz

Submission #53512

# Submission time Handle Problem Language Result Execution time Memory
53512 2018-06-30T06:47:35 Z 노영훈(#1418) Salesman (IOI09_salesman) C++11
50 / 100
 1000 ms 24208 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[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;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15992 KB Output is correct
2 Correct 14 ms 16104 KB Output is correct
3 Correct 14 ms 16188 KB Output is correct
4 Correct 16 ms 16232 KB Output is correct
5 Correct 20 ms 16232 KB Output is correct
6 Correct 48 ms 18376 KB Output is correct
7 Correct 113 ms 18684 KB Output is correct
8 Correct 258 ms 19372 KB Output is correct
9 Correct 338 ms 20008 KB Output is correct
10 Correct 517 ms 21844 KB Output is correct
11 Correct 640 ms 21844 KB Output is correct
12 Correct 739 ms 22868 KB Output is correct
13 Correct 721 ms 22996 KB Output is correct
14 Correct 995 ms 24044 KB Output is correct
15 Correct 812 ms 24116 KB Output is correct
16 Execution timed out 1079 ms 24188 KB Time limit exceeded
17 Incorrect 19 ms 24188 KB Output isn't correct
18 Incorrect 18 ms 24188 KB Output isn't correct
19 Incorrect 15 ms 24188 KB Output isn't correct
20 Incorrect 17 ms 24188 KB Output isn't correct
21 Incorrect 21 ms 24188 KB Output isn't correct
22 Incorrect 21 ms 24188 KB Output isn't correct
23 Incorrect 20 ms 24188 KB Output isn't correct
24 Incorrect 20 ms 24188 KB Output isn't correct
25 Incorrect 214 ms 24188 KB Output isn't correct
26 Incorrect 362 ms 24188 KB Output isn't correct
27 Incorrect 630 ms 24188 KB Output isn't correct
28 Incorrect 621 ms 24188 KB Output isn't correct
29 Execution timed out 1000 ms 24208 KB Time limit exceeded
30 Incorrect 949 ms 24208 KB Output isn't correct