Submission #1026967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026967		Tob	Salesman (IOI09_salesman)	C++14	100 / 100	495 ms	65536 KiB

salesman

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 5e5 + 7, ofs = (1 << 19);
const ll inf = 1e18;

int n, u, d, s;
ll ti[N], h[N], c[N], dp[N];
vector <int> g[N];

struct T {
	ll non;
	vector <ll> t;
	void init(ll non_) {
		non = non_;
		t.clear(); t.resize(2*ofs, non);
	}
	void update(int x, ll val) {
		x += ofs;
		t[x] = max(t[x], val);
		while (x /= 2) t[x] = max(t[2*x], t[2*x+1]);
	}
	ll query(int x, int a, int b, int lo = 0, int hi = ofs-1) {
		if (b < lo || hi < a) return non;
		if (a <= lo && hi <= b) return t[x];
		int mid = (lo + hi) / 2;
		return max(query(2*x, a, b, lo, mid), query(2*x+1, a, b, mid+1, hi));
	}
} t1, t2;

int main () {
	FIO;
	cin >> n >> u >> d >> s; s--;
	
	t1.init(-inf); t2.init(-inf);
	for (int i = 0; i < n; i++) {
		cin >> ti[i] >> h[i] >> c[i];
		ti[i]--; h[i]--;
		g[ti[i]].pb(i);
	}
	for (int i = N-1; i >= 0; i--) {
		if (g[i].empty()) continue;
		sort(all(g[i]), [&](int x, int y) {return h[x] < h[y];});
		int siz = g[i].size();
		vector <ll> v(siz, -inf), suf(siz+1, -inf), pre(siz+1, -inf);
		for (int j = siz-1; j >= 0; j--) {
			int x = g[i][j];
			v[j] = max((h[x] > s) ? u*(s-h[x]) : d*(h[x]-s), max(-h[x]*u+t1.query(1, 0, h[x]), h[x]*d+t2.query(1, h[x], N)));
			suf[j] = max(suf[j+1]+c[x], v[j]+c[x] - d*h[x]);
		}
		for (int j = 0; j < siz; j++) {
			int x = g[i][j];
			pre[j+1] = max(pre[j]+c[x], v[j]+c[x] + u*h[x]);
			dp[x] = max(pre[j+1] - u*h[x], suf[j] + d*h[x]);
		}
		for (int x : g[i]) {
			t1.update(h[x], dp[x]+u*h[x]);
			t2.update(h[x], dp[x]-d*h[x]);
		}
	}
	ll res = max(0LL, max(-s*u+t1.query(1, 0, s), s*d+t2.query(1, s, N)));
	cout << res << "\n";

	return 0;
}

• Subtask 1: 100 / 100