oj.uz

Submission #874626

# Submission time Handle Problem Language Result Execution time Memory
874626 2023-11-17T12:28:16 Z sjoonmin07 Salesman (IOI09_salesman) C++17
60 / 100
 502 ms 58452 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using pii=pair<int,int>;

const int inf=1e9;
int N,S,U,D,M,n;
vector<pii> v[505050];
struct Mart {
    int t,x,m;
} Q[505050];
bool cmp1(Mart a,Mart b) {
    if(a.t==b.t) return a.x<b.x;
    return a.t<b.t;
}

struct Seg {
    int T[2020202];
    void update(int s,int e,int num,int key,ll val) {
        if(e<key||key<s) return;
        if(s==e) {
            T[num]=val; return;
        }
        int mid=(s+e)/2;
        update(s,mid,num*2,key,val); update(mid+1,e,num*2+1,key,val);
        T[num]=max(T[num*2],T[num*2+1]);
    }
    int query(int s,int e,int num,int l,int r) {
        if(e<l||r<s) return -inf;
        if(l<=s&&e<=r) return T[num];
        int mid=(s+e)/2;
        return max(query(s,mid,num*2,l,r),query(mid+1,e,num*2+1,l,r));
    }
} L,R;

int main() {
    scanf("%d%d%d%d",&N,&U,&D,&S);
    for(int i=1;i<=N;i++) scanf("%d%d%d",&Q[i].t,&Q[i].x,&Q[i].m);
    sort(Q+1,Q+N+1,cmp1);
    Q[0].t=0;
    n=S;
    for(int i=1;i<=N;i++) {
        if(Q[i].t!=Q[i-1].t) v[++M].eb(pii(Q[i].x,Q[i].m));
        else v[M].eb(pii(Q[i].x,Q[i].m));
        n=max(n,Q[i].x);
    }
    v[++M].eb(pii(S,0));
    n+= n==S;
    for(int i=1;i<=4*n;i++) L.T[i]=-inf,R.T[i]=-inf;
    L.update(1,n,1,S,U*S); R.update(1,n,1,S,-D*S);
    for(int i=1;i<=M+1;i++) {
        int l=v[i].size();
        vector<int> upres(l),downres(l);
        for(int j=0;j<l;j++) {
            auto &[x,m]=v[i][j];
            int val=L.query(1,n,1,1,x);
            if(j==0) {
                if(val==-inf) upres[j]=-inf;
                else upres[j]=val-x*U+m;
            } else {
                if(val==-inf&&upres[j-1]==-inf) upres[j]=-inf;
                else upres[j]=max(upres[j-1]+(v[i][j-1].fi-x)*U,val-x*U)+m;
            }
        }
        for(int j=l-1;j>=0;j--) {
            auto &[x,m]=v[i][j];
            int val=R.query(1,n,1,x,n);
            if(j==l-1) {
                if(val==-inf) downres[j]=-inf;
                else downres[j]=val+x*D+m;
            } else {
                if(val==-inf&&downres[j+1]==-inf) downres[j]=-inf;
                else downres[j]=max(downres[j+1]+(x-v[i][j+1].fi)*D,val+x*D)+m;
            }
        }
        for(int j=0;j<l;j++) {
            int val=max(upres[j],downres[j]),x=v[i][j].fi;
            if(val==-inf) continue;
            L.update(1,n,1,x,val+U*x); R.update(1,n,1,x,val-D*x);
        }
    }
    printf("%d",L.query(1,n,1,S,S)-U*S);
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d%d%d%d",&N,&U,&D,&S);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:42:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(int i=1;i<=N;i++) scanf("%d%d%d",&Q[i].t,&Q[i].x,&Q[i].m);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17240 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 5 ms 17496 KB Output is correct
5 Correct 7 ms 17756 KB Output is correct
6 Correct 27 ms 30916 KB Output is correct
7 Correct 57 ms 32180 KB Output is correct
8 Correct 110 ms 36692 KB Output is correct
9 Correct 148 ms 39024 KB Output is correct
10 Correct 272 ms 47956 KB Output is correct
11 Correct 315 ms 48776 KB Output is correct
12 Correct 401 ms 52656 KB Output is correct
13 Correct 401 ms 52948 KB Output is correct
14 Correct 502 ms 58452 KB Output is correct
15 Correct 435 ms 57640 KB Output is correct
16 Correct 482 ms 57688 KB Output is correct
17 Incorrect 3 ms 17240 KB Output isn't correct
18 Incorrect 3 ms 17244 KB Output isn't correct
19 Incorrect 4 ms 17500 KB Output isn't correct
20 Incorrect 5 ms 17500 KB Output isn't correct
21 Incorrect 5 ms 17472 KB Output isn't correct
22 Incorrect 7 ms 17500 KB Output isn't correct
23 Incorrect 6 ms 17500 KB Output isn't correct
24 Incorrect 7 ms 17520 KB Output isn't correct
25 Incorrect 83 ms 34132 KB Output isn't correct
26 Incorrect 161 ms 36896 KB Output isn't correct
27 Incorrect 270 ms 42592 KB Output isn't correct
28 Incorrect 305 ms 43428 KB Output isn't correct
29 Incorrect 382 ms 44852 KB Output isn't correct
30 Incorrect 390 ms 47128 KB Output isn't correct