oj.uz

Submission #249900

# Submission time Handle Problem Language Result Execution time Memory
249900 2020-07-16T11:23:32 Z mode149256 Salesman (IOI09_salesman) C++14
0 / 100
 70 ms 65540 KB 
/*input
4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll INF = 1e12;
struct ST
{
	ll mx = -INF;
	ll lazy = -INF;
	int l, r;
	ST *left;
	ST *right;
	ST(ll l, ll r): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST(l, (l + r) / 2);
			right = new ST((l + r) / 2 + 1, r);
		}
	}
	void fix()
	{
		if (l < r)
		{
			left->lazy = max(left->lazy, lazy);
			right->lazy = max(right->lazy, lazy);
		}

		lazy = -INF;
	}
	void set(ll a, ll b, ll gal)
	{
		if (a <= l && r <= b)
		{
			lazy = max(lazy, gal);
			mx = max(mx, lazy);
			return;
		}

		mx = max(mx, lazy);

		if (b < l || r < a) {
			return;
		}

		fix();
		left->set(a, b, gal);
		right->set(a, b, gal);
		mx = max(left->mx, right->mx);
	}
	ll get(ll i)
	{
		mx = max(mx, lazy);
		fix();

		if (l == r) {
			return mx;
		}

		if (i <= (l + r) / 2) {
			return left->get(i);
		}
		else {
			return right->get(i);
		}
	}
};
ST MX1(0, 500001);
ST MX2(0, 500001);
int P[500001], T[500001], X[500001];
int A[500001];
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0), cerr.tie(0);
	ll N, U, D, S;
	cin >> N >> U >> D >> S;

	for (ll i = 0; i < N; i++) {
		cin >> T[i] >> X[i] >> P[i];
	}

	for (ll i = 0; i < N; i++) {
		A[i] = i;
	}

	sort(A, A + N, [&](ll a, ll b) {
		return T[a] < T[b];
	});
	ll ans = 0;
	MX1.set(S, 500001, S * D);
	MX2.set(0, S, -S * U);
	vector<int>visi;

	for (int j = 0; j < N; j++)
	{
		visi.push_back(A[j]);

		if (j + 1 < N && T[A[j]] == T[A[j + 1]]) {
			continue;
		}

		sort(visi.begin(), visi.end(), [&](int a, int b) {
			return X[a] < X[b];
		});
		int n = visi.size();
		vector<ll>Suf(n);
		vector<ll>Pre(n);

		for (int i = 0; i < n; i++)
			Suf[i] = Pre[i] = ll(P[visi[i]]) + max(
								  -ll(X[visi[i]]) * D + MX1.get(X[visi[i]]),
								  ll(X[visi[i]]) * U + MX2.get(X[visi[i]])
							  );

		for (int i = 1; i < n; i++) {
			Pre[i] = max(Pre[i], Pre[i - 1] + P[visi[i]] - D * ll(X[visi[i]] - X[visi[i - 1]]));
		}

		for (int i = n - 2; i >= 0; i--) {
			Suf[i] = max(Suf[i], Suf[i + 1] + P[visi[i]] - U * ll(X[visi[i + 1]] - X[visi[i]]));
		}

		for (int i = 0; i < n; i++)
		{
			ll maxi = max(Suf[i], Pre[i]);
			MX1.set(X[visi[i]], 500001, maxi + ll(X[visi[i]]) * D);
			MX2.set(0, X[visi[i]], maxi - ll(X[visi[i]]) * U);

			if (X[visi[i]] >= S)
			{
				ans = max(ans, maxi - ll(X[visi[i]] - S) * U);
			}
			else
			{
				ans = max(ans, maxi - ll(S - X[visi[i]]) * D);
			}
		}

		visi.clear();
	}

	cout << ans << "\n";
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 70 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 70 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 65 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 66 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 67 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 63 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 65 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 66 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 68 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 66 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 66 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 63 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 65 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 63 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 63 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 60 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 68 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 67 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 64 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 64 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 67 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 65 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 66 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 66 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 65 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)