Submission #1171109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171109		Dan4Life	Salesman (IOI09_salesman)	C++17	6 / 100	3097 ms	33364 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<int,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;
	for(int i = 1; i <= n; i++) dp[i]=-LINF;
	for(int i = 0; i < n; i++){
		int t, l, m; 
		cin >> t >> l >> m; 
		v[t].pb({l,m});
	}
	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-1]+(l[j]<l[i]?U:D)*abs(l[i]-l[j])+c[i]);
			}
		}
		for(int i = cnt-1; i >= lst; i--){
			for(int j = lst+1; j < cnt; j++){
				best[i] = max(best[i], dp[j]+pref[j-1]-pref[i+1]);
			}
		}
		for(int i = lst; i < cnt; i++) dp[i]=max(dp[i],best[i]);
	}
	for(int i = 0; i <= n; i++) 
		ans=max(ans, dp[i]+(l[0]<l[i]?D:U)*abs(l[i]-l[0]));
	cout << ans << "\n";
}

• Subtask 1: 6 / 100