oj.uz

Submission #68907

# Submission time Handle Problem Language Result Execution time Memory
68907 2018-08-19T08:17:06 Z KLPP Salesman (IOI09_salesman) C++14
90 / 100
 1000 ms 47780 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 31608 KB Output is correct
2 Correct 41 ms 31836 KB Output is correct
3 Correct 35 ms 31836 KB Output is correct
4 Correct 44 ms 31840 KB Output is correct
5 Correct 40 ms 32100 KB Output is correct
6 Correct 75 ms 32524 KB Output is correct
7 Correct 149 ms 33096 KB Output is correct
8 Correct 254 ms 34364 KB Output is correct
9 Correct 331 ms 35500 KB Output is correct
10 Correct 548 ms 39036 KB Output is correct
11 Correct 632 ms 39076 KB Output is correct
12 Correct 898 ms 41508 KB Output is correct
13 Correct 939 ms 41508 KB Output is correct
14 Execution timed out 1075 ms 43776 KB Time limit exceeded
15 Correct 853 ms 43848 KB Output is correct
16 Execution timed out 1008 ms 43848 KB Time limit exceeded
17 Correct 34 ms 43848 KB Output is correct
18 Correct 36 ms 43848 KB Output is correct
19 Correct 36 ms 43848 KB Output is correct
20 Correct 39 ms 43848 KB Output is correct
21 Correct 44 ms 43848 KB Output is correct
22 Correct 45 ms 43848 KB Output is correct
23 Correct 44 ms 43848 KB Output is correct
24 Correct 42 ms 43848 KB Output is correct
25 Correct 237 ms 43848 KB Output is correct
26 Correct 390 ms 43848 KB Output is correct
27 Correct 607 ms 43868 KB Output is correct
28 Correct 711 ms 43868 KB Output is correct
29 Correct 945 ms 44280 KB Output is correct
30 Correct 892 ms 47780 KB Output is correct