Submission #441447

#	Time	Username	Problem	Language	Result	Execution time	Memory
441447		dutch	Salesman (IOI09_salesman)	C++17	100 / 100	422 ms	19876 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p a[i][1]

const int INF = 1e18, H = 5e5+2;

void z(int &a, int b){ a = max(a, b); }

struct FenwickTree{
	vector<int> a; int n, i, f;
	FenwickTree(int N, bool flipped) : a((n=N)+1, -INF), f(flipped) {}
	FenwickTree& operator[](int j){ i = f ? n-j : j+1; return *this; }
	void operator=(int v){
		for(; i<=n; i+=i&-i) z(a[i], v);
	}
	int operator()(int j){
		i = f ? n-j : j+1; int s = -INF;
		for(; i>=1; i-=i&-i) z(s, a[i]);
		return s;
	}
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	int n, u, d, s; cin >> n >> u >> d >> s;
	d = -d, u = -u;
	array<int, 3> a[n]; // day, location, profitability
	for(auto &i : a){
		cin >> i[0] >> i[1] >> i[2];
	}
	sort(a, a+n);

	FenwickTree dpD(H, 1), dpU(H, 0);
	dpD[s] = s * d, dpU[s] = - s * u;

	for(int l=0; l<n; ){
		int r = l+1;
		while(r<n && a[l][0] == a[r][0]) ++r;

		for(int i=l; i<r; ++i){
			a[i][0] = -INF;
			z(a[i][0], dpD(p) - p * d);
			z(a[i][0], p * u + dpU(p));
		}

		int pre = -INF, suf = -INF, sum = 0;

		for(int i=l; i<r; ++i){
			z(pre, a[i][0] - p * u - sum);
			sum += a[i][2];
			dpD[p] = (pre + sum + p * u) + p * d;
			dpU[p] = (pre + sum + p * u) - p * u;
		}

		sum = 0;

		for(int i=r-1; i>=l; --i){
			z(suf, a[i][0] + p * d - sum);
			sum += a[i][2];
			dpD[p] = (suf + sum - p * d) + p * d;
			dpU[p] = (suf + sum - p * d) - p * u;
		}

		l = r;
	}

	int ans = 0;
	ans = max(ans, dpD(s) - s * d);
	ans = max(ans, dpU(s) + s * u);
	cout << ans;
}

• Subtask 1: 100 / 100