Submission #68715

#	Time	Username	Problem	Language	Result	Execution time	Memory
68715		KLPP	Salesman (IOI09_salesman)	C++14	42 / 100	1098 ms	47836 KiB

salesman

#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long int lld;
#define INF 1000000000000
#define MAXL 500010
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);
}
class ST{
	lld segtree[4*MAXL];
	int N;
	public:
		void build(int a, int b, int node){
			segtree[node]=-INF;
			if(a==b)return;
			int mid=(a+b)/2;
			build(a,mid,2*node);
			build(mid+1,b,2*node+1);
		}
		void Build(int n){
			build(0,n-1,1);
			N=n;
		}
		void update(int pos,lld val, int a, int b, int node){//cout<<a<<" "<<b<<endl;
			if(a>pos || pos>b)return;
			if(a==b){
				segtree[node]=max(segtree[node],val);
				return;
			}
			int mid=(a+b)/2;
			update(pos,val,a,mid,2*node);
			update(pos,val,mid+1,b,2*node+1);
			segtree[node]=max(segtree[2*node],segtree[2*node+1]);
		}
		void Update(int pos,lld val){
			update(pos,val,0,N-1,1);
		}
		lld query(int x, int y, int a, int b, int node){
			if(b<x || a>y)return -INF;
			if(x<=a && b<=y)return segtree[node];
			int mid=(a+b)/2;
			lld p1=query(x,y,a,mid,2*node);
			lld p2=query(x,y,mid+1,b,2*node+1);
			return max(p1,p2);
		}
		lld Query(int x, int y){
			return query(x,y,0,N-1,1);
		}
};
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;
	ST *s1=new ST();
	
	s1->Build(MAXL);
	//s1->Update(s,0);
	//cout<<s1->Query(0,MAXL-1)<<endl;
	ST *s2=new ST();
	s2->Build(MAXL);
	s1->Update(s,0-u*s);
	s2->Update(s,0+d*s);
	for(int i=0;i<=n;i++){
		if(i>0 && fairs[i].first!=fairs[i-1].first){
			for(int j=prev;j<i;j++){
				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);
					}
				}*/
				DP[l]=max(DP[l],fairs[j].second.second+s2->Query(0,l-1)-d*l);
				//cout<<fairs[j].second.second+s1->Query(0,l-1)-u*l<<endl;
				DP[l]=max(DP[l],fairs[j].second.second+s1->Query(l+1,MAXL-1)+u*l);
				//cout<<fairs[j].second.second+s2->Query(l+1,MAXL-1)+d*l<<endl;
				s1->Update(l,DP[l]-u*l);
				s2->Update(l,DP[l]+d*l);
			}
			prev=i;
		}
	}
	lld ans=0;
	/*for(int i=0;i<n;i++){
		cout<<DP[fairs[i].second.first]<<" "<<fairs[i].first<<endl;	
	}cout<<endl;*/
	ans=max(ans,s2->Query(0,s-1)-d*s);
	ans=max(ans,s1->Query(s+1,MAXL-1)+u*s);
	/*for(int i=0;i<MAXL;i++){
		ans=max(ans,DP[i]-cost(i,s));
	}*/printf("%lld",ans);
	//cout<<cost(100,120)<<endl;
	


	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:57: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:62: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: 42 / 100