Submission #247451

#	Time	Username	Problem	Language	Result	Execution time	Memory
247451		mode149256	Salesman (IOI09_salesman)	C++14	0 / 100	520 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 = 1e14;
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);
	vi laikai(N);

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


	vector<vpi> fair;
	{
		sort(laikai.begin(), laikai.end());

		unordered_map<int, int> kas;
		int piv = 0;

		for (int i = 0; i < N; ++i)
		{
			if (!i or laikai[i] != laikai[i - 1])
				kas[laikai[i]] = piv++;
		}

		fair.resize(kas.size());
		for (int i = 0; i < N; ++i)
		{
			fair[kas[sk[i].x]].emplace_back(sk[i].y);
		}
	}

	for (auto && u : fair)
		sort(u.begin(), u.end());

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

	// node nuoPradBeM(1, L);
	// node nuoPabBeM(1, L);

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

	for (auto vec : fair) {
		if (vec.size() == 1) {
			int l = vec[0].x;
			int m = vec[0].y;

			int naujasPrad = -l * D + nuoPrad.get(1, l);
			int naujasPab = l * U + nuoPab.get(l, L);
			// dp[i] = min(naujas);
			// printf("l = %d, m = %d, dp = %intd\n", l, m, max(naujasPrad, naujasPab) + m);
			nuoPrad.upd(l, D * l + max(naujasPrad, naujasPab) + m);
			nuoPab.upd(l, -U * l + max(naujasPrad, naujasPab) + m);
			// nuoPradBeM.upd(l, D * l + max(naujasPrad, naujasPab));
			// nuoPabBeM.upd(l, -U * l + max(naujasPrad, naujasPab));
		} else {
			vi nauja;

			for (auto pora : vec) {
				int l = pora.x;

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

				nauja.emplace_back(max(naujasPrad, naujasPab));
			}

			for (int i = 0; i < (int)vec.size(); ++i)
			{
				int l = vec[i].x;
				int m = vec[i].y;
				nuoPrad.upd(l, D * l + nauja[i] + m);
				nuoPab.upd(l, -U * l + nauja[i] + m);
				// nuoPradBeM.upd(l, D * l + nauja[i]);
				// nuoPabBeM.upd(l, -U * l + nauja[i]);
			}

			{
				int p = vec[0].x * (D + U);
				int suma = vec[0].y;

				int nxt = nuoPab.get(vec[0].x, vec[0].x) + p;
				for (int i = 1; i < vec.size(); ++i)
				{
					suma += vec[i].y;
					int l = vec[i].x;

					int val = -l * D + suma + nxt;

					nuoPrad.upd(l, D * L + val);
					nuoPab.upd(l, -U * l + val);

					p = max(p, -(suma - vec[i].y) + l * (D + U));
					nxt = min(nxt, nuoPab.get(vec[i].x, vec[i].x) + p);
				}
			}

			{
				int p = vec.back().x * (D + U);
				int suma = vec.back().y;

				int nxt = nuoPrad.get(vec.back().x, vec.back().x) + p;
				for (int i = (int)vec.size() - 2; i >= 0; i--)
				{
					suma += vec[i].y;
					int l = vec[i].x;

					int val = +l * U + suma + nxt;

					nuoPrad.upd(l, D * L + val);
					nuoPab.upd(l, -U * l + val);

					p = max(p, -(suma - vec[i].y) - l * (D + U));
					nxt = max(nxt, nuoPrad.get(vec[i].x, vec[i].x) + p);
				}
			}

			// for (int i = 0; i < vec.size(); ++i)
			// {
			// 	int l = vec[i].x;
			// 	int m = vec[i].y;
			// 	nuoPradBeM.upd(l, nuoPrad.get(l, l) - m);
			// 	nuoPabBeM.upd(l, nuoPab.get(l, l) - m);
			// }
		}
	}

	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
*/

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:189:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < vec.size(); ++i)
                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 100