Submission #376389

#	Time	Username	Problem	Language	Result	Execution time	Memory
376389		kimjg1119	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	26 ms	24704 KiB

merchant

#include <bits/stdc++.h>

/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/

#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
#define double long double

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
typedef unsigned long long ull;

const int MOD = 1000000007; // PLZ check
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

struct SegmentTreeMax {
	int sz;
	vector<ll> a;

	SegmentTreeMax(int _sz) : sz(_sz), a(sz * 4 + 10, -LINF) {}

	void update(int nd, int s, int e, int x, ll v) {
		if (e < x || x < s) return;
		if (s == e && x == s) {
			a[nd] = max(a[nd], v);
			return;
		}
		int m = (s + e) >> 1;
		update(nd << 1, s, m, x, v);
		update(nd << 1 | 1, m + 1, e, x, v);
		a[nd] = max(a[nd << 1], a[nd << 1 | 1]);
	}

	void update(int x, ll v) { update(1, 0, sz - 1, x, v); }

	ll query(int nd, int s, int e, int l, int r) {
		if (e < l || r < s) return -LINF;
		if (l <= s && e <= r) return a[nd];
		int m = (s + e) >> 1;
		return max(query(nd << 1, s, m, l, r), query(nd << 1 | 1, m + 1, e, l, r));
	}

	ll query(int l, int r) { return query(1, 0, sz - 1, l, r); }
};

ll n, u, d, s;
vector<int> fair[505050];
ll pos[505050], score[505050];
ll dp[505050];

const int K = 500005;

int main() {
	fio();
	cin >> n >> u >> d >> s;
	for (int i = 0; i < n; i++) {
		int t1;
		cin >> t1 >> pos[i] >> score[i];
		fair[t1].push_back(i);
	}
	fair[K - 1].push_back(n);
	pos[n] = s;
	for (int i = 0; i <= K; i++) {
		sort(all(fair[i]), [&](int a, int b) {
			return pos[a] < pos[b];
			});
	}
	for (int i = 0; i <= K + 10; i++)
		dp[i] = -LINF;

	SegmentTreeMax segd(505050), segu(505050);
	for (int day = 0; day <= K; day++) {
		ll d1, d2;
		for (int h : fair[day]) {
			d1 = pos[h] < s ? (pos[h] - s) * u : (s - pos[h]) * d;
			d1 = max(d1, segd.query(0, pos[h] - 1) + (K - pos[h]) * d); // down
			d1 += score[h];
			dp[h] = max(dp[h], d1);
			segd.update(pos[h], d1 - (K - pos[h]) * d);
		}
		reverse(all(fair[day]));
		for (int h : fair[day]) {
			d2 = pos[h] < s ? (pos[h] - s) * u : (s - pos[h]) * d;
			d2 = max(d2, segu.query(pos[h] + 1, K) + pos[h] * u); // up
			d2 += score[h];
			dp[h] = max(dp[h], d2);
			segu.update(pos[h], d2 - pos[h] * u);
		}
		for (int h : fair[day]) {
			segd.update(pos[h], dp[h] - (K - pos[h]) * d);
			segu.update(pos[h], dp[h] - pos[h] * u);
		}
	}
	/*for (int i = 0; i <= n; i++) cout << dp[i] << ends;
	cout << endl;*/
	cout << dp[n];
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34