Submission #1171126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171126		Dan4Life	Salesman (IOI09_salesman)	C++17	40 / 100	26 ms	20300 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<ll,2>;
const int mxN = (int)5e5+10;
const ll LINF = (ll)1e17;

ll l[mxN], c[mxN];
vector<ar2> v[mxN];
ll n, U, D, s, ans, cnt=1;
ll best[mxN], pref[mxN], dp[mxN];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> D >> U >> l[0]; U*=-1, D*=-1;
	if(n>5000) exit(0); //remove later
	for(int i = 1; i < mxN; i++) dp[i]=best[i]=-LINF;
	for(int i = 0; i < n; i++){
		int t, l, m; 
		cin >> t >> l >> m; 
		v[t].pb({l,m});
	}
	v[mxN-1].pb({l[0],0});
	for(int _ = 1; _ < mxN; _++){
		if(!sz(v[_])) continue; 
		sort(all(v[_]));
		int lst = cnt; pref[lst-1] = 0;
		for(auto [x,m] : v[_]) l[cnt++]=x, c[cnt-1]=m; 
		for(int i = lst; i < cnt; i++) pref[i]=pref[i-1]+c[i];
		for(int i = lst; i < cnt; i++){
			for(int j = 0; j < lst; j++){
				dp[i] = max(dp[i], dp[j]+(l[j]<l[i]?U:D)*abs(l[i]-l[j])+c[i]);
			}
		}
		ll xd = -LINF;
		for(int i = lst; i < cnt; i++){
			best[i] = max(best[i], xd+U*l[i]+pref[i]);
			xd = max(xd, dp[i]-pref[i]-U*l[i]);
		}
		xd = -LINF;
		for(int i = cnt-1; i >= lst; i--){
			best[i] = max(best[i], xd-D*l[i]-pref[i-1]);
			xd = max(xd, dp[i]+pref[i-1]+D*l[i]);
		}
		for(int i = lst; i < cnt; i++) dp[i]=max(dp[i],best[i]);
	}
	cout << dp[n+1] << "\n";
}

• Subtask 1: 40 / 100