oj.uz

Submission #53509

# Submission time Handle Problem Language Result Execution time Memory
53509 2018-06-30T06:43:18 Z 노영훈(#1418) Salesman (IOI09_salesman) C++11
40 / 100
 1000 ms 24264 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;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15920 KB Output is correct
2 Correct 15 ms 16060 KB Output is correct
3 Correct 15 ms 16060 KB Output is correct
4 Correct 18 ms 16060 KB Output is correct
5 Correct 28 ms 16176 KB Output is correct
6 Correct 81 ms 18272 KB Output is correct
7 Correct 155 ms 18656 KB Output is correct
8 Correct 332 ms 19332 KB Output is correct
9 Correct 424 ms 19992 KB Output is correct
10 Correct 714 ms 21780 KB Output is correct
11 Correct 821 ms 21780 KB Output is correct
12 Execution timed out 1039 ms 22896 KB Time limit exceeded
13 Execution timed out 1045 ms 22896 KB Time limit exceeded
14 Execution timed out 1066 ms 23996 KB Time limit exceeded
15 Execution timed out 1081 ms 24032 KB Time limit exceeded
16 Execution timed out 1088 ms 24264 KB Time limit exceeded
17 Incorrect 16 ms 24264 KB Output isn't correct
18 Incorrect 20 ms 24264 KB Output isn't correct
19 Incorrect 19 ms 24264 KB Output isn't correct
20 Incorrect 18 ms 24264 KB Output isn't correct
21 Incorrect 26 ms 24264 KB Output isn't correct
22 Incorrect 23 ms 24264 KB Output isn't correct
23 Incorrect 26 ms 24264 KB Output isn't correct
24 Incorrect 28 ms 24264 KB Output isn't correct
25 Incorrect 272 ms 24264 KB Output isn't correct
26 Incorrect 550 ms 24264 KB Output isn't correct
27 Execution timed out 1016 ms 24264 KB Time limit exceeded
28 Execution timed out 1035 ms 24264 KB Time limit exceeded
29 Execution timed out 1075 ms 24264 KB Time limit exceeded
30 Execution timed out 1088 ms 24264 KB Time limit exceeded