Submission #68907

#	Time	Username	Problem	Language	Result	Execution time	Memory
68907		KLPP	Salesman (IOI09_salesman)	C++14	90 / 100	1075 ms	47780 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];
			if(segtree[node]==-INF)return -INF;
			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){
			vector<lld> A;
			for(int j=prev;j<i;j++){
				int l=fairs[j].second.first;
				lld a=-INF;
				a=max(a,fairs[j].second.second+s2->Query(0,l-1)-d*l);
				//cout<<fairs[j].second.second+s1->Query(0,l-1)-u*l<<endl;
				a=max(a,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,a-u*l);
				s2->Update(l,a+d*l);*/
				A.push_back(a);
			}
			lld upstreamK[i-prev];
			lld downstreamK[i-prev];
			downstreamK[0]=A[0];
			for(int j=prev+1;j<i;j++){
downstreamK[j-prev]=max(A[j-prev],downstreamK[j-prev-1]+fairs[j].second.second-d*(fairs[j].second.first-fairs[j-1].second.first));
			}//for(int j=prev;j<i;j++)cout<<downstreamK[j-prev]<<endl;
			upstreamK[i-1-prev]=A[i-1-prev];
			for(int j=i-2;j>=prev;j--){
upstreamK[j-prev]=max(A[j-prev],upstreamK[j-prev+1]+fairs[j].second.second-u*(fairs[j+1].second.first-fairs[j].second.first));
			}//for(int j=prev;j<i;j++)cout<<upstreamK[j-prev]<<endl;
			lld doubledown[i-prev];
			lld doubleup[i-prev];
			doubledown[0]=0;
			for(int j=prev+1;j<i;j++){
doubledown[j-prev]=max((lld)0,doubledown[j-prev-1]-(u+d)*(fairs[j].second.first-fairs[j-1].second.first)+fairs[j-1].second.second);
			}//for(int j=prev;j<i;j++)cout<<doubledown[j-prev]<<endl;
			doubleup[i-prev-1]=0;
			for(int j=i-2;j>=prev;j--){
doubleup[j-prev]=max((lld)0,doubleup[j-prev+1]-(u+d)*(fairs[j+1].second.first-fairs[j].second.first)+fairs[j+1].second.second);
			}//for(int j=prev;j<i;j++)cout<<doubleup[j-prev]<<endl;
			for(int j=prev;j<i;j++){
				A[j-prev]=max(upstreamK[j-prev]+doubledown[j-prev],downstreamK[j-prev]+doubleup[j-prev]);
				s1->Update(fairs[j].second.first,A[j-prev]-u*fairs[j].second.first);
				s2->Update(fairs[j].second.first,A[j-prev]+d*fairs[j].second.first);
				//cout<<A[j-prev]<<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;*/
	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\n",ans);
	//cout<<cost(100,120)<<endl;
	


	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:58: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:63: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: 90 / 100