Submission #69557

#	Time	Username	Problem	Language	Result	Execution time	Memory
69557		gnoor	Salesman (IOI09_salesman)	C++17	0 / 100	1101 ms	66560 KiB

salesman

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

long long treeu[2000100];
long long treed[2000100];
long long xu[2000100];
long long xd[2000100];

long long u,d;

void update(long long *seg,int idx,int l,int r,long long c,int k,long long val) {
	if (l+1==r) {
		seg[idx]=max(seg[idx],c*l+val);
		return;
	}
	int m=(l+r)>>1;
	if (k<m) update(seg,idx*2+1,l,m,c,k,val);
	else update(seg,idx*2+2,m,r,c,k,val);
	seg[idx]=max(seg[idx*2+1],seg[idx*2+2]);
}

void reset(int idx,int l,int r,int k) {
	if (l+1==r) {
		xd[idx]=-1e18;
		xu[idx]=-1e18;
		return;
	}
	int m=(l+r)>>1;
	if (k<m) reset(idx*2+1,l,m,k);
	else reset(idx*2+2,m,r,k);
	xd[idx]=xu[idx]=-1e18;
}

long long query(long long *seg,int idx,int l,int r,int ll,int rr) {
	if (rr<=l||ll>=r) return -1e18;
	if (ll<=l&&rr>=r) return seg[idx];
	int m=(l+r)>>1;
	return max(query(seg,idx*2+1,l,m,ll,rr),query(seg,idx*2+2,m,r,ll,rr));
}

struct event {
	int pos,cost;
};

bool operator< (const event &a, const event &b) {
	return a.pos<b.pos;
}

vector<event> e[500100];

int main () {
	int n,s;
	scanf("%d%lld%lld%d",&n,&u,&d,&s);
	for (int i=0;i<2000100;i++) {
		treeu[i]=-1e18;
		treed[i]=-1e18;
		xu[i]=-1e18;
		xd[i]=-1e18;
	}
	int a,b,c;
	for (int i=0;i<n;i++) {
		scanf("%d%d%d",&a,&b,&c);
		e[a].push_back(event{b,c});
	}
	for (int i=1;i<500005;i++) {
		sort(e[i].begin(),e[i].end());
	}
	update(treeu,0,1,500005,-u,s,0);
	update(treed,0,1,500005,d,s,0);
	long long cur;
	
	for (int j=0;j<500005;j++) {
		vector<long long> qs(e[j].size()+1,0);
		for (int i=0;i<(int)e[j].size();i++) {
			qs[i+1]=qs[i]+e[j][i].cost;
		}
		for (int i=0;i<(int)e[j].size();i++) {
			cur=max(query(treeu,0,1,500005,e[j][i].pos+1,500005)+e[j][i].pos*u,query(treed,0,1,500005,1,e[j][i].pos)-e[j][i].pos*d);
			update(xu,0,1,500005,-u,e[j][i].pos,cur+qs[i+1]);
			update(xd,0,1,500005,d,e[j][i].pos,cur-qs[i]);
		}
		for (int i=0;i<(int)e[j].size();i++) {
			cur=max(query(xu,0,1,500005,e[j][i].pos,500005)+e[j][i].pos*u-qs[i],query(xd,0,1,500005,1,e[j][i].pos)-e[j][i].pos*d+qs[i+1]);
			update(treeu,0,1,500005,-u,e[j][i].pos,cur);
			update(treed,0,1,500005,d,e[j][i].pos,cur);
		}
		for (int i=0;i<(int)e[j].size();i++) {
			reset(0,1,500005,e[j][i].pos);
		}
	}
	long long ans=max(query(treeu,0,1,500005,s,500005)+s*u,query(treed,0,1,500005,1,s)-s*d);
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld%d",&n,&u,&d,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100