Submission #589285

#	Time	Username	Problem	Language	Result	Execution time	Memory
589285		Drew_	Salesman (IOI09_salesman)	C++17	100 / 100	798 ms	56140 KiB

salesman

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

using ll = long long;
using ii = pair<int, int>;

const int MAX = 5e5 + 69;
const ll inf = (ll)1e18 + 69;

struct Segtree
{
	ll st[2*MAX];	
	Segtree() { fill(st, st + 2*MAX, -inf); }

	inline void modify(int p, ll val)
	{
		for (st[p += MAX] = val; p > 1; p >>= 1)
			st[p >> 1] = max(st[p], st[p^1]);
	}

	inline ll query(int l, int r)
	{
		ll res = -inf;
		for (l += MAX, r += MAX+1; l < r; l >>= 1, r >>= 1)
		{
			if (l & 1) res = max(res, st[l++]);
			if (r & 1) res = max(res, st[--r]);
		}
		return res;
	}
};

int N, U, D, S;
vector<ii> fair[MAX];

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> U >> D >> S;
	for (int i = 0, t, l, m; i < N; ++i)
	{
		cin >> t >> l >> m;
		fair[t].pb({l, m});
	}

	ll val[MAX]; fill(val, val + MAX, -inf);
	Segtree stU, stD; // stU[x]: val[x] - x*u, stD[x]: val[x] + x*d
	
	val[S] = 0;
	stU.modify(S, -S*U);
	stD.modify(S, S*D);

	for (int t = 0; t < MAX; ++t) if (!fair[t].empty())
	{
		sort(fair[t].begin(), fair[t].end());
		for (auto &[l, m] : fair[t])
		{
			ll a = stU.query(l, MAX-60), b = stD.query(1, l);
			a += l*U; b -= l*D;

			val[l] = max(val[l], max(a, b));
			stU.modify(l, val[l] - l*U);
			stD.modify(l, val[l] + l*D);
		}

		vector<pair<int, ll>> pend;
		for (auto &[l, m] : fair[t])
		{
			ll best = stD.query(1, l);
			best += -l*D + m;
			best = max(best, val[l]);

			pend.pb({l, best});
			stD.modify(l, best + l*D);
		}

		reverse(fair[t].begin(), fair[t].end());
		for (auto &[l, m] : fair[t])
		{
			ll best = stU.query(l, MAX-60);
			best += l*U + m;
			best = max(best, val[l]);

			pend.pb({l, best});
			stU.modify(l, best - l*U);
		}

		for (auto &[l, tmp] : pend)
			val[l] = max(val[l], tmp);

		for (auto &[l, m] : fair[t])
		{
			stU.modify(l, val[l] - l*U);
			stD.modify(l, val[l] + l*D);
		}
	}

	cout << max(stD.query(1, S) - S*D, stU.query(S, MAX-60) + S*U) << '\n';

	return 0;
}

• Subtask 1: 100 / 100