Submission #758134

#	Time	Username	Problem	Language	Result	Execution time	Memory
758134		SanguineChameleon	Salesman (IOI09_salesman)	C++17	17 / 100	3081 ms	47616 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 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]) {
			dp[i] = fairs[i].prof - (fairs[i].loc < start ? up * (start - fairs[i].loc) : down * (fairs[i].loc - start));
			for (int j = 1; j <= n; j++) {
				if (j == i || dp[j] == -inf) {
					continue;
				}
				dp[i] = max(dp[i], fairs[i].prof + dp[j] - (j < i ? down * (fairs[i].loc - fairs[j].loc) : up * (fairs[j].loc - fairs[i].loc)));
			}
			tmp[i] = dp[i];
		}
		assert((int)group[day].size() == 1);
		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), 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), tmp[j]);
			dp[j] = max(dp[j], best);
		}
	}
	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: 17 / 100