Submission #69530

#	Time	Username	Problem	Language	Result	Execution time	Memory
69530		gnoor	Salesman (IOI09_salesman)	C++17	30 / 100	1050 ms	66560 KiB

salesman

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

using namespace std;

long long treeu[2000100];
long long treed[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]);
}

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 day,pos,cost;
};

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

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;
	}
	for (int i=0;i<n;i++) {
		scanf("%d%d%d",&e[i].day,&e[i].pos,&e[i].cost);
	}
	sort(e,e+n);
	update(treeu,0,1,500005,-u,s,0);
	update(treed,0,1,500005,d,s,0);
	long long cur;
	for (int i=0;i<n;i++) {
		cur=max(query(treeu,0,1,500005,e[i].pos+1,500005)+e[i].pos*u,query(treed,0,1,500005,1,e[i].pos)-e[i].pos*d);
		cur+=e[i].cost;
		update(treeu,0,1,500005,-u,e[i].pos,cur);
		update(treed,0,1,500005,d,e[i].pos,cur);
	}
	long long ans=max(query(treeu,0,1,500005,s+1,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:42: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&e[i].day,&e[i].pos,&e[i].cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100