Submission #874626

#	Time	Username	Problem	Language	Result	Execution time	Memory
874626		sjoonmin07	Salesman (IOI09_salesman)	C++17	60 / 100	502 ms	58452 KiB

salesman

#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 (stderr)

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 / 100