Submission #249898

#	Time	Username	Problem	Language	Result	Execution time	Memory
249898		mode149256	Salesman (IOI09_salesman)	C++14	0 / 100	300 ms	65540 KiB

salesman

/*input
4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) {
	return pair<T, T>(a.x + b.x, a.y + b.y);
}
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) {
	return pair<T, T>(a.x - b.x, a.y - b.y);
}
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) {
	return (a.x * b.x + a.y * b.y);
}
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) {
	return (a.x * b.y - a.y * b.x);
}

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;

	for (auto u : vec) {
		cout << u << ' ';
	}

	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;

struct node {
	int l, r;
	int did;
	node *left = nullptr;
	node *right = nullptr;

	node(int a, int b): l(a), r(b), did(-MOD) {
		if (l != r) {
			left = new node(l, (l + r) / 2);
			right = new node((l + r) / 2 + 1, r);
		}
	}

	void upd(int pos, int val) {
		if (l == r) {
			assert(l == pos);
			did = max(did, val);
			return;
		}
		else if (pos <= (l + r) / 2) {
			left->upd(pos, val);
		}
		else {
			right->upd(pos, val);
		}

		did = max(left->did, right->did);
	}

	int get(int a, int b) {
		if (r < a or b < l) {
			return -MOD;
		}
		else if (a <= l and r <= b) {
			return did;
		}
		else {
			return max(left->get(a, b), right->get(a, b));
		}
	}
};
int N, U, D, S;
int L = 500005;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> U >> D >> S;
	vector<pair<int, pi>> sk(N);

	for (int i = 0; i < N; ++i)
	{
		int t, l, m;
		cin >> t >> l >> m;
		sk[i] = {t, {l, m}};
	}

	sort(sk.begin(), sk.end(), [](const pair<int, pi> &a, const pair<int, pi> &b) {
		return a.x < b.x;
	});

	node nuoPrad(1, L);
	node nuoPab(1, L);

	nuoPrad.upd(S, D * S);
	nuoPab.upd(S, -U * S);

	vpi vec;

	for (int h = 0; h < N; ++h)
	{
		vec.emplace_back(sk[h].y);

		if (h + 1 < N and sk[h].x == sk[h + 1].x) {
			continue;
		}

		sort(vec.begin(), vec.end(), [](const pi & a , const pi & b) {
			return a.x < b.x;
		});
		int n = (int)vec.size();

		vi pre(n);
		vi suf(n);

		for (int j = 0; j < n; ++j)
		{
			int l = vec[j].x;
			int m = vec[j].y;
			pre[j] = suf[j] = m + max(-l * D + nuoPrad.get(1, l), l * U + nuoPab.get(l, L));
		}

		for (int i = 1; i < n; ++i)
		{
			pre[i] = max(pre[i], pre[i - 1] - D * (vec[i].x - vec[i - 1].x) + vec[i].y);
		}

		for (int i = n - 2; i >= 0; --i)
		{
			suf[i] = max(suf[i], suf[i + 1] - U * (vec[i + 1].x - vec[i].x) + vec[i].y);
		}

		for (int i = 0; i < n; ++i)
		{
			int did = max(pre[i], suf[i]);

			nuoPrad.upd(vec[i].x, D * vec[i].x + did);
			nuoPab.upd(vec[i].x, -U * vec[i].x + did);
		}

		vec.clear();
	}

	int naujasPrad = -S * D + nuoPrad.get(1, S);
	int naujasPab = S * U + nuoPab.get(S, L);

	printf("%d\n", max(naujasPrad, naujasPab));
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

• Subtask 1: 0 / 100