Submission #133799

#	Time	Username	Problem	Language	Result	Execution time	Memory
133799		figter001	Salesman (IOI09_salesman)	C++17	41 / 100	975 ms	48248 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int nax = 5e5 + 100;

vector<pair<int,int>> e[nax];
ll n,U,D,s,len;
ll up[4*nax],dn[4*nax];
ll dp[nax];

void init(){
	for(int i=1;i<=len;i++)dp[i] = -1e10;
	dp[s] = 0;
}

void build(int n,int s,int e){
	if(s == e){
		up[n] = dp[s] + s * U;
		dn[n] = dp[s] - s * D;
		return;
	}
	build(n*2,s,(s+e)/2);
	build(n*2+1,(s+e)/2+1,e);
	up[n] = max(up[n*2] , up[n*2+1]);
	dn[n] = max(dn[n*2] , dn[n*2+1]);
}

void update(int n,int s,int e,int at){
	if(s > at || e < at)return;
	if(s == e){
		up[n] = dp[s] - s * U;
		dn[n] = dp[s] + s * D;
		return;
	}
	update(n*2,s,(s+e)/2,at);
	update(n*2+1,(s+e)/2+1,e,at);
	up[n] = max(up[n*2] , up[n*2+1]);
	dn[n] = max(dn[n*2] , dn[n*2+1]);
}

ll get(int n,int s,int e,int l,int r,int t){
	if(s > r || e < l)return -1e18;
	if(s >= l && e <= r){
		if(t == 0)return up[n];
		else if(t == 1)return dn[n];
	}
	return max( get(n*2,s,(s+e)/2,l,r,t) , get(n*2+1,(s+e)/2+1,e,l,r,t) );
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout << fixed;
	cin>>n>>U>>D>>s;
	len = s;
	e[0].push_back({s,0});
	int mxd=0;
	for(int i=1;i<n;i++){
		int d,l,m;
		cin>>d>>l>>m;
		e[d].push_back({l,m});
		len = max(len,1ll*l);
		mxd = max(mxd,d);
	}
	mxd++;
	e[mxd].push_back({s,0});
	len++;
	init();
	build(1,1,len);
	for(int day=0;day<=mxd;day++){
		if(e[day].empty())continue;
		if(e[day].size() == 1){
			int l = e[day][0].first;
			int m = e[day][0].second;
			ll cur = -1e18;
			if(day != 0){
				cur = max(cur, get(1,1,len,1,l,1) + m - D*l);
				cur = max(cur, get(1,1,len,l,len,0) + m + U*l);
			}
			dp[l] = max(dp[l],cur);
			update(1,1,len,l);
		}else{

		}
	}
	cout << dp[s] << endl;
}

• Subtask 1: 41 / 100