Submission #328392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
328392	2020-11-16T11:48:03 Z	XGN	Salesman (IOI09_salesman)	C++17	62 / 100	648 ms	41692 KB

salesman

/*
Though leaves are many, the root is one;
Through all the lying days of my youth
I swayed my leaves and flowers in the sun,
Now may I wither into the truth.

- William Butler Yeats
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
#include <bitset>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;

#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
/**==Info==
*Program:1
*Problem:Salesman
*Date:2020-11-16
*Algorithm:60pts DP and Data Structure
*Status:Unknown*/

bool debug=false;

struct Fair{
	int day;
	int pos;
	int val;
};

ll n,u,d,s;
Fair fair[500005];

bool cmp(Fair a,Fair b){
	if(a.day!=b.day){
		return a.day<b.day;
	}
	if(a.pos!=b.pos){
		return a.pos<b.pos;
	}
	return a.val<b.val;
}

inline ll calcPrice(int x,int y){
	if(x<y){
		return (y-x)*d;
	}else{
		return (x-y)*u;
	}
}

int posIndex[500005];
vector<pii> v;

const ll inf=1e15;

struct Seg{
	int n;
	ll node[2000005];
	
	void build(int nn){
		n=1;
		while(n<nn){
			n<<=1;
		}
		fill(node,node+2*n,-inf);
	}
	
	void modify(int pos,ll val){
		pos+=n;
		node[pos]=val;
		while(pos){
			pos>>=1;
			node[pos]=max(node[pos<<1],node[pos<<1|1]);
		}
	}
	
	ll query(int l,int r){
		l+=n;
		r+=n;
		ll mx=-inf;
		while(l<=r){
			if(l%2==1){
				mx=max(mx,node[l]);
				l++;
			}
			if(r%2==0){
				mx=max(mx,node[r]);
				r--;
			}
			l>>=1;
			r>>=1;
		}
		
		return mx;
	}
};

Seg segL,segR;

ll dp[500005];

int main(int argc,char* argv[]){
//	freopen("1.in","r",stdin);
	
	qi;
	cin>>n>>u>>d>>s;
	
	segL.build(n);
	segR.build(n);
	
	for(int i=0;i<n;i++){
		cin>>fair[i].day>>fair[i].pos>>fair[i].val;
	}
	
	sort(fair,fair+n,cmp);
	
	for(int i=0;i<n;i++){
		v.push_back(make_pair(fair[i].pos,i));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++){
		posIndex[v[i].second]=i;
	}
	
	
	for(int i=n-1;i>=0;i--){
		ll down=segL.query(0,posIndex[i])-fair[i].pos*u;
		ll up=segR.query(posIndex[i],n-1)+fair[i].pos*d;
		
//		cout<<i<<" "<<down<<" "<<up<<" "<<-calcPrice(fair[i].pos,s)<<endl;
		
		dp[i]=max({
			down,
			up,
			-calcPrice(fair[i].pos,s) //go home
		})+fair[i].val;
		
		segL.modify(posIndex[i],dp[i]+fair[i].pos*u);
		segR.modify(posIndex[i],dp[i]-fair[i].pos*d);
	}
	
//	for(int i=0;i<n;i++){
//		cout<<dp[i]<<" ";
//	}
	ll ans=0;
	for(int i=0;i<n;i++){
		ans=max(ans,dp[i]-calcPrice(s,fair[i].pos));
	}
	
	cout<<ans<<endl;
	return 0;
}

Subtask #1

62.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	4 ms	876 KB	Output is correct
6	Correct	17 ms	2544 KB	Output is correct
7	Correct	44 ms	5100 KB	Output is correct
8	Correct	100 ms	9704 KB	Output is correct
9	Correct	155 ms	15844 KB	Output is correct
10	Correct	294 ms	31068 KB	Output is correct
11	Correct	370 ms	31708 KB	Output is correct
12	Correct	501 ms	35548 KB	Output is correct
13	Correct	512 ms	35932 KB	Output is correct
14	Correct	632 ms	41692 KB	Output is correct
15	Correct	506 ms	40636 KB	Output is correct
16	Correct	648 ms	40668 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Incorrect	1 ms	364 KB	Output isn't correct
19	Incorrect	1 ms	492 KB	Output isn't correct
20	Incorrect	2 ms	620 KB	Output isn't correct
21	Incorrect	3 ms	620 KB	Output isn't correct
22	Incorrect	4 ms	1004 KB	Output isn't correct
23	Incorrect	4 ms	876 KB	Output isn't correct
24	Incorrect	7 ms	876 KB	Output isn't correct
25	Incorrect	84 ms	9192 KB	Output isn't correct
26	Incorrect	190 ms	17892 KB	Output isn't correct
27	Incorrect	332 ms	32492 KB	Output isn't correct
28	Incorrect	417 ms	33244 KB	Output isn't correct
29	Incorrect	533 ms	39260 KB	Output isn't correct
30	Incorrect	531 ms	40156 KB	Output isn't correct