Submission #68697

#	Time	Username	Problem	Language	Result	Execution time	Memory
68697		KLPP	Salesman (IOI09_salesman)	C++14	15 / 100	292 ms	66560 KiB

salesman

#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long int lld;
#define INF 1000000000000
#define MAXL 6000
int n,u,d,s;
lld DP[MAXL];
lld cost(int start,int end){
	if(start>end)return u*(start-end);
	return d*(end-start);
}
int main(){
	scanf("%d %d %d %d",&n,&u,&d,&s);
	vector<pair<int,pair<int,lld> > >fairs;
	for(int i=0;i<n;i++){
		int time,l;
		lld s;
		scanf("%d %d %lld",&time,&l,&s);
		fairs.push_back(pair<int,pair<int,lld> >(time,pair<int,lld>(l,s)));
	}
	sort(fairs.begin(),fairs.end());
	for(int i=0;i<MAXL;i++)DP[i]=-INF;
	DP[s]=0;
	int prev=0;
	for(int i=0;i<=n;i++){
		if(i>0 && fairs[i].first!=fairs[i-1].first){
			for(int j=prev;j<i;j++){//cout<<j<<" "<<fairs[j].second.second<<" ";
				int l=fairs[j].second.first;
				for(int k=0;k<MAXL;k++){
					if(DP[k]!=-INF && DP[l]<DP[k]+fairs[j].second.second-cost(k,l) && k!=l){
						DP[l]=DP[k]+fairs[j].second.second-cost(k,l);
						//cout<<k<<endl;
					}
				}
				//cout<<DP[l]<<endl;
			}
			prev=i;
		}
	}
	lld ans=0;
	/*for(int i=0;i<n;i++){
		cout<<DP[fairs[i].second.first]<<" "<<fairs[i].first<<endl;	
	}cout<<endl;*/
	for(int i=0;i<MAXL;i++){
		ans=max(ans,DP[i]-cost(i,s));
	}cout<<ans<<endl;
	//cout<<cost(100,120)<<endl;
	


	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:16: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:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&time,&l,&s);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 100