Submission #758157

#	Time	Username	Problem	Language	Result	Execution time	Memory
758157		SanguineChameleon	Salesman (IOI09_salesman)	C++17	100 / 100	488 ms	41488 KiB

salesman

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct fair {
	int day, loc, prof;
};

bool operator<(fair f1, fair f2) {
	return f1.loc < f2.loc;
}

const int inf = 1e9 + 20;
const int maxn = 5e5 + 20;
fair fairs[maxn];
vector<int> group[maxn];
int bit_l[maxn];
int bit_r[maxn];
int dp[maxn];
int tmp[maxn];
int n, down, up, start;

void update(int bit[], int pos, int val) {
	for (int i = pos; i <= n; i += i & (-i)) {
		bit[i] = max(bit[i], val);
	}
}

int get(int bit[], int pos) {
	int res = -inf;
	for (int i = pos; i > 0; i -= i & (-i)) {
		res = max(res, bit[i]);
	}
	return res;
}

void just_do_it() {
	cin >> n >> up >> down >> start;
	for (int i = 1; i <= n; i++) {
		cin >> fairs[i].day >> fairs[i].loc >> fairs[i].prof;
		dp[i] = -inf;
		bit_l[i] = -inf;
		bit_r[i] = -inf;
	}
	sort(fairs + 1, fairs + n + 1);
	for (int i = 1; i <= n; i++) {
		group[fairs[i].day].push_back(i);
	}
	for (int day = 1; day < maxn; day++) {
		if (group[day].empty()) {
			continue;
		}
		for (auto i: group[day]) {
			tmp[i] = fairs[i].prof - (fairs[i].loc < start ? up * (start - fairs[i].loc) : down * (fairs[i].loc - start));
			int best_l = get(bit_l, i) + fairs[i].prof - down * fairs[i].loc;
			int best_r = get(bit_r, n + 1 - i) + fairs[i].prof + up * fairs[i].loc;
			tmp[i] = max(tmp[i], best_l);
			tmp[i] = max(tmp[i], best_r);
		}
		for (auto i: group[day]) {
			dp[i] = tmp[i];
		}
		int best = tmp[group[day][0]];
		for (int pos = 1; pos < (int)group[day].size(); pos++) {
			int i = group[day][pos - 1];
			int j = group[day][pos];
			best = max(best - down * (fairs[j].loc - fairs[i].loc) + fairs[j].prof, tmp[j]);
			dp[j] = max(dp[j], best);
		}
		best = tmp[group[day].back()];
		for (int pos = (int)group[day].size() - 2; pos >= 0; pos--) {
			int i = group[day][pos + 1];
			int j = group[day][pos];
			best = max(best - up * (fairs[i].loc - fairs[j].loc) + fairs[j].prof, tmp[j]);
			dp[j] = max(dp[j], best);
		}
		for (auto i: group[day]) {
			update(bit_l, i, dp[i] + down * fairs[i].loc);
			update(bit_r, n + 1 - i, dp[i] - up * fairs[i].loc);
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res = max(res, dp[i] - (fairs[i].loc < start ? down * (start - fairs[i].loc) : up * (fairs[i].loc - start)));
	}
	cout << res;
}

• Subtask 1: 100 / 100