Submission #551607

#	Time	Username	Problem	Language	Result	Execution time	Memory
551607		1bin	Salesman (IOI09_salesman)	C++14	60 / 100	794 ms	48080 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 5e5 + 5;
ll n, d, u, s, x, m, t, base = 1, ans, dp[NMAX];
ll seg1[1 << 20], seg2[1 << 20];
vector<pair<ll, ll>> v[NMAX];

void upd1(int idx, ll v) {
	idx += base;
	while (idx) {
		seg1[idx] = max(seg1[idx], v);
		idx /= 2;
	}
	return;
}

void upd2(int idx, ll v) {
	idx += base;
	while (idx) {
		seg2[idx] = max(seg2[idx], v);
		idx /= 2;
	}
	return;
}

ll mx1(int l, int r) {
	ll ret = -1e18;
	l += base; r += base;
	while (l <= r) {
		if (l & 1) ret = max(ret, seg1[l++]);
		if (!(r & 1)) ret = max(ret, seg1[r--]);
		l /= 2; r /= 2;
	}
	return ret;
}

ll mx2(int l, int r) {
	ll ret = -1e18;
	l += base; r += base;
	while (l <= r) {
		if (l & 1) ret = max(ret, seg2[l++]);
		if (!(r & 1)) ret = max(ret, seg2[r--]);
		l /= 2; r /= 2;
	}
	return ret;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> u >> d >> s;
	for (int i = 0; i < n; i++) {
		cin >> t >> x >> m;
		v[t].emplace_back(x, m);
	}

	base = 1 << 19;
	for (int i = 1; i < base * 2; i++) seg1[i] = seg2[i] = -1e18;
	dp[s] = 0; upd1(s, d * s); upd2(s, -u * s);

	for (int t = 0; t < NMAX; t++) {
		if (v[t].empty()) continue;
		sort(all(v[t]));
		for (auto& [x, m] : v[t]) {
			dp[x] = max(-d * x + mx1(0, x - 1), u * x + mx2(x + 1, base - 1));
			upd1(x, d * x + dp[x]);  upd2(x, -u * x + dp[x]);
		}

		for (auto& [x, m] : v[t]) {
			dp[x] = -d * x + mx1(0, x - 1) + m;
			upd1(x, d * x + dp[x]);
		}
		for (int i = v[t].size() - 1; i >= 0; i--) {
			auto& [x, m] = v[t][i];
			ll y = u * x + mx2(x + 1, base - 1) + m;
			dp[x] = max(dp[x], y);
			upd2(x, -u * x + y);
		}
		for (auto& [x, m] : v[t]) {
			upd1(x, d * x + dp[x]); upd2(x, -u * x + dp[x]);
			if (x > s) ans = max(ans, -u * (x - s) + dp[x]);
			else ans = max(ans, -d * (s - x) + dp[x]);
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   for (auto& [x, m] : v[t]) {
      |              ^
salesman.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |   for (auto& [x, m] : v[t]) {
      |              ^
salesman.cpp:78:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |    auto& [x, m] = v[t][i];
      |          ^
salesman.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for (auto& [x, m] : v[t]) {
      |              ^

• Subtask 1: 60 / 100