oj.uz

Submission #53576

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

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 {
    ll 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, 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 -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));
    }
    ll mx(int l, int r){
        if(r<l) return -inf;
        return mx(1,1,n,l,r);
    }
} US, DS;

ll D[MX];

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

int get(int x){
    ll 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(XMX);
    US.init(XMX);
    for(int i=1; i<=n; i++)
        upt(i,-inf);
    upt(s, 0);
    for(int i=1; i<=n; i++){
        ll 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 14 ms 17528 KB Output is correct
2 Correct 14 ms 17528 KB Output is correct
3 Correct 17 ms 17672 KB Output is correct
4 Correct 17 ms 17880 KB Output is correct
5 Correct 24 ms 17904 KB Output is correct
6 Correct 62 ms 21984 KB Output is correct
7 Correct 131 ms 22504 KB Output is correct
8 Correct 281 ms 23000 KB Output is correct
9 Correct 307 ms 23588 KB Output is correct
10 Correct 566 ms 25280 KB Output is correct
11 Correct 655 ms 25320 KB Output is correct
12 Correct 790 ms 26504 KB Output is correct
13 Correct 807 ms 26504 KB Output is correct
14 Execution timed out 1058 ms 27820 KB Time limit exceeded
15 Correct 930 ms 27820 KB Output is correct
16 Execution timed out 1084 ms 27820 KB Time limit exceeded
17 Incorrect 15 ms 27820 KB Output isn't correct
18 Incorrect 15 ms 27820 KB Output isn't correct
19 Incorrect 17 ms 27820 KB Output isn't correct
20 Incorrect 18 ms 27820 KB Output isn't correct
21 Incorrect 18 ms 27820 KB Output isn't correct
22 Incorrect 21 ms 27820 KB Output isn't correct
23 Incorrect 21 ms 27820 KB Output isn't correct
24 Incorrect 25 ms 27820 KB Output isn't correct
25 Incorrect 232 ms 27820 KB Output isn't correct
26 Incorrect 403 ms 27820 KB Output isn't correct
27 Incorrect 786 ms 27820 KB Output isn't correct
28 Incorrect 750 ms 27820 KB Output isn't correct
29 Execution timed out 1067 ms 27820 KB Time limit exceeded
30 Execution timed out 1074 ms 27820 KB Time limit exceeded