oj.uz

답안 #53517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53517 2018-06-30T06:52:41 Z 노영훈(#1418) Salesman (IOI09_salesman) C++11
60 / 100
 1000 ms 16788 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;
        int m=1;
        for(; m<=2*n; m*=2);
        for(int i=1; i<m; 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
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 8 ms 8616 KB Output is correct
3 Correct 13 ms 8756 KB Output is correct
4 Correct 10 ms 8792 KB Output is correct
5 Correct 14 ms 8792 KB Output is correct
6 Correct 48 ms 10888 KB Output is correct
7 Correct 107 ms 11352 KB Output is correct
8 Correct 199 ms 12000 KB Output is correct
9 Correct 293 ms 12720 KB Output is correct
10 Correct 502 ms 14216 KB Output is correct
11 Correct 568 ms 14344 KB Output is correct
12 Correct 795 ms 15564 KB Output is correct
13 Correct 744 ms 15576 KB Output is correct
14 Correct 921 ms 16668 KB Output is correct
15 Correct 759 ms 16668 KB Output is correct
16 Correct 986 ms 16668 KB Output is correct
17 Incorrect 11 ms 16668 KB Output isn't correct
18 Incorrect 9 ms 16668 KB Output isn't correct
19 Incorrect 10 ms 16668 KB Output isn't correct
20 Incorrect 11 ms 16668 KB Output isn't correct
21 Incorrect 11 ms 16668 KB Output isn't correct
22 Incorrect 15 ms 16668 KB Output isn't correct
23 Incorrect 15 ms 16668 KB Output isn't correct
24 Incorrect 14 ms 16668 KB Output isn't correct
25 Incorrect 203 ms 16668 KB Output isn't correct
26 Incorrect 354 ms 16668 KB Output isn't correct
27 Incorrect 630 ms 16668 KB Output isn't correct
28 Incorrect 603 ms 16668 KB Output isn't correct
29 Execution timed out 1083 ms 16788 KB Time limit exceeded
30 Execution timed out 1028 ms 16788 KB Time limit exceeded