Submission #133606

#	Time	Username	Problem	Language	Result	Execution time	Memory
133606		figter001	Salesman (IOI09_salesman)	C++17	60 / 100	958 ms	37784 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;

int d[nax],l[nax],m[nax];
int n,U,D,s,len;
ll up[4*nax],dn[4*nax];
ll dp[nax];

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;
	n+=2;
	d[0] = -1;l[0] = s;
	d[n-1] = nax + 1;l[n-1] = s;
	len = s;
	for(int i=1;i<n;i++){
		cin>>d[i]>>l[i]>>m[i];
		len = max(len,l[i]);
	}
	len++;
	vector<int> idx;
	for(int i=0;i<n;i++)idx.push_back(i);
	sort(idx.begin(),idx.end(), [&] (int a,int b) {
		return d[a] < d[b];
	});
	for(int i=1;i<=len;i++)dp[i] = -1e10;
	dp[s] = 0;
	build(1,1,len);
	for(int i : idx){
		ll cur = -1e18;
		if(i != 0){
			cur = max(cur, get(1,1,len,1,l[i],1) + m[i] - D*l[i]);
			cur = max(cur, get(1,1,len,l[i],len,0) + m[i] + U*l[i]);
		}
		dp[l[i]] = max(dp[l[i]],cur);
		update(1,1,len,l[i]);
	}
	cout << dp[s] << endl;
}

• Subtask 1: 60 / 100