Submission #139556

#	Time	Username	Problem	Language	Result	Execution time	Memory
139556		Boxworld	Salesman (IOI09_salesman)	C++14	17 / 100	1091 ms	18992 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
const int N=500100;
struct fair{int day,dis,val;}a[N];
int n,u,d,s;
long long ans[N];
bool cmp(fair x,fair y){return x.day<y.day;}
long long cost(int x1,int x2){
	if (x1<x2)return (x2-x1)*u;
	return (x1-x2)*d;
}
int main(){
	scanf("%d%d%d%d",&n,&u,&d,&s);
	a[0].dis=a[n+1].dis=s;
	a[0].val=a[n+1].val=0;
	for (int i=1;i<=n;i++)scanf("%d%d%d",&a[i].day,&a[i].dis,&a[i].val);
	sort(a+1,a+n+1,cmp);
	memset(ans,0,sizeof(ans));
	ans[0]=0;
	for (int i=1;i<=n+1;i++)ans[i]=-cost(a[0].dis,a[i].dis);
	for (int i=1;i<=n+1;i++)
	for (int j=0;j<i;j++)
	ans[i]=max(ans[i],ans[j]-cost(a[j].dis,a[i].dis)+a[i].val);
	printf("%lld\n",ans[n+1]);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&u,&d,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:16:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1;i<=n;i++)scanf("%d%d%d",&a[i].day,&a[i].dis,&a[i].val);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 100