Submission #1171114

#TimeUsernameProblemLanguageResultExecution timeMemory
1171114Dan4LifeSalesman (IOI09_salesman)C++17
16 / 100
31 ms16344 KiB
#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]=-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]);
			}
		}
		for(int i = lst; i < cnt; i++){
			for(int j = lst; j < i; j++){
				best[i] = max(best[i], dp[j]-pref[j]+pref[i]+(l[j]<l[i]?U:D)*abs(l[i]-l[j]));
			}
		}
		for(int i = cnt-1; i >= lst; i--){
			for(int j = i+1; j < cnt; j++){
				best[i] = max(best[i], dp[j]+pref[j-1]-pref[i-1]+(l[j]<l[i]?U:D)*abs(l[i]-l[j]));
			}
		}
		for(int i = lst; i < cnt; i++) dp[i]=max(dp[i],best[i]);
	}
	cout << dp[n+1] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...