Submission #758147

#	Time	Username	Problem	Language	Result	Execution time	Memory
758147		SanguineChameleon	Salesman (IOI09_salesman)	C++17	46 / 100	3069 ms	41356 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 val_l[maxn];
int val_r[maxn];
int dp[maxn];
int tmp[maxn];
int n, down, up, start;

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;
	}
	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 = -inf;
			int best_r = -inf;
			for (int j = 1; j <= i; j++) {
				best_l = max(best_l, dp[j] + down * fairs[j].loc);
			}
			best_l += fairs[i].prof - down * fairs[i].loc;
			for (int j = i; j <= n; j++) {
				best_r = max(best_r, dp[j] - up * fairs[j].loc);
			}
			best_r += 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]) {
			val_l[i] = dp[i] + down * fairs[i].loc;
			val_r[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: 46 / 100