제출 #551603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551603		1bin	Salesman (IOI09_salesman)	C++14	62 / 100	695 ms	56928 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;
		for (int i = v[t].size() - 1; i >= 0; i--) {
			auto& [x, m] = v[t][i];
			dp[x] = max(dp[x], u * x + mx2(x + 1, base - 1) + m);
			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;
}

컴파일 시 표준 에러 (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]) dp[x] = -d * x + mx1(0, x - 1) + m;
      |              ^
salesman.cpp:75:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |    auto& [x, m] = v[t][i];
      |          ^

• Subtask 1: 62 / 100