Submission #376197

#	Time	Username	Problem	Language	Result	Execution time	Memory
376197		urd05	Salesman (IOI09_salesman)	C++14	60 / 100	2251 ms	65536 KiB

salesman

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
 
const int sz=524288;
 
struct SegmentTree {
    long long seg[sz*2];
    long long lazy[sz*2];
    void init() {
        for(int i=1;i<sz*2;i++) {
            seg[i]=-1e12;
            lazy[i]=-1e12;
        }
    }
    void propagate(int node) {
        if (node<sz) {
            lazy[node*2]=max(lazy[node*2],lazy[node]);
            lazy[node*2+1]=max(lazy[node*2+1],lazy[node]);
        }
        seg[node]=max(seg[node],lazy[node]);
    }
    long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        propagate(node);
        if (l>r||r<nodel||l>noder) {
            return -1e12;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }
    void update(int l,int r,long long val,int node=1,int nodel=0,int noder=sz-1) {
        propagate(node);
        if (r<nodel||l>noder) {
            return;
        }
        if (l<=nodel&&noder<=r) {
            lazy[node]=max(lazy[node],val);
            propagate(node);
            return;
        }
        int mid=(nodel+noder)/2;
        update(l,r,val,node*2,nodel,mid);
        update(l,r,val,node*2+1,mid+1,noder);
        seg[node]=max(seg[node*2],seg[node*2+1]);
    }
};
 
SegmentTree st1; //val[i]+Di
SegmentTree st2; //val[i]-Ui
long long dp[500000];
long long le[500000];
long long ri[500000];
long long psum[500001];
 
int n,u,d,s;
typedef pair<int,int> P;
vector<P> vec[500001];
 
int main(void) {
    scanf("%d %d %d %d",&n,&u,&d,&s);
    for(int i=0;i<n;i++) {
        int t,l,m;
        scanf("%d %d %d",&t,&l,&m);
        vec[t].push_back(P(l,m));
    }
    st1.init();
    st2.init();
    st1.update(s,s,d*s);
    st2.update(s,s,-u*s);
    for(int i=1;i<=500000;i++) {
        if (vec[i].empty()) {
            continue;
        }
        sort(vec[i].begin(),vec[i].end());
        psum[0]=0;
        for(int j=1;j<=vec[i].size();j++) {
            psum[j]=psum[j-1]+vec[i][j-1].second;
        }
        for(int j=0;j<vec[i].size();j++) {
            le[j]=-1e12;
            ri[j]=-1e12;
        }
        long long mx=st1.sum(0,vec[i][0].first-1);
        for(int j=0;j<vec[i].size();j++) {
            le[j]=max(le[j],mx+psum[j+1]-d*vec[i][j].first);
            mx=max(mx,st1.sum(vec[i][j].first,vec[i][j].first)-psum[j]);
        }
        mx=st2.sum(vec[i].back().first+1,sz-1)+psum[vec[i].size()];
        for(int j=vec[i].size()-1;j>=0;j--) {
            ri[j]=max(ri[j],mx+u*vec[i][j].first-psum[j]);
            mx=max(mx,st2.sum(vec[i][j].first,vec[i][j].first)+psum[j+1]);
        }
        for(int j=0;j<vec[i].size();j++) {
            long long val=max(le[j],ri[j]);
            st1.update(vec[i][j].first,sz-1,val+d*vec[i][j].first);
            st2.update(0,vec[i][j].first,val-u*vec[i][j].first);
        }
    }
    long long ret=0;
    for(int i=0;i<sz;i++) {
        long long val=max(st1.sum(i,i)-d*i,st2.sum(i,i)+u*i);
        if (i<s) {
            val-=d*(s-i);
        }
        else {
            val-=u*(i-s);
        }
        ret=max(ret,val);
    }
    printf("%lld",ret);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int j=1;j<=vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~~
salesman.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%d %d %d",&t,&l,&m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100