Submission #589285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
589285	2022-07-04T11:50:37 Z	Drew_	Salesman (IOI09_salesman)	C++17	100 / 100	798 ms	56140 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	19 ms	31604 KB	Output is correct
3	Correct	19 ms	31572 KB	Output is correct
4	Correct	23 ms	31584 KB	Output is correct
5	Correct	22 ms	31796 KB	Output is correct
6	Correct	54 ms	32596 KB	Output is correct
7	Correct	92 ms	34072 KB	Output is correct
8	Correct	166 ms	36532 KB	Output is correct
9	Correct	235 ms	38668 KB	Output is correct
10	Correct	388 ms	45736 KB	Output is correct
11	Correct	522 ms	46376 KB	Output is correct
12	Correct	605 ms	50248 KB	Output is correct
13	Correct	620 ms	50548 KB	Output is correct
14	Correct	765 ms	56140 KB	Output is correct
15	Correct	675 ms	55244 KB	Output is correct
16	Correct	798 ms	55344 KB	Output is correct
17	Correct	18 ms	31528 KB	Output is correct
18	Correct	19 ms	31572 KB	Output is correct
19	Correct	20 ms	31640 KB	Output is correct
20	Correct	19 ms	31584 KB	Output is correct
21	Correct	19 ms	31648 KB	Output is correct
22	Correct	22 ms	31776 KB	Output is correct
23	Correct	21 ms	31768 KB	Output is correct
24	Correct	22 ms	31828 KB	Output is correct
25	Correct	154 ms	34340 KB	Output is correct
26	Correct	227 ms	38020 KB	Output is correct
27	Correct	379 ms	43752 KB	Output is correct
28	Correct	459 ms	43948 KB	Output is correct
29	Correct	662 ms	43500 KB	Output is correct
30	Correct	575 ms	48288 KB	Output is correct