Submission #328392

#	Time	Username	Problem	Language	Result	Execution time	Memory
328392		XGN	Salesman (IOI09_salesman)	C++17	62 / 100	648 ms	41692 KiB

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 / 100