Submission #330616

#	Time	Username	Problem	Language	Result	Execution time	Memory
330616		MetB	Salesman (IOI09_salesman)	C++14	98 / 100	526 ms	16536 KiB

salesman

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const int N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int n, U, D, s, maxx;

struct SegTree {
	vector<int> t;
	int start;

	void build (int n) {
		start = 1;
		while (start < n) start <<= 1;
		t = vector <int> (2 * start, -2e9);
	}

	void update (int x, int d) {
		x += start;

		t[x] = d;
		x >>= 1;

		while (x) {
			t[x] = max (t[2 * x], t[2 * x + 1]);
			x >>= 1;
		}
	}

	int get (int l, int r) {
		l += start, r += start + 1;

		int mx = -2e9;

		while (l < r) {
			if (l & 1) mx = max (mx, t[l++]);
			if (r & 1) mx = max (mx, t[--r]);
			l >>= 1, r >>= 1;
		}

		return mx;
	}
} t_left, t_right;

struct shop {
	int x, t, m;

	bool operator< (shop& b) {
		return t < b.t;
	}
} a[N];

void process (int l, int r) {

	vector <shop> v (a + l, a + r);
	vector <int> ans (r - l), ans_l (r - l), ans_r (r - l);

	sort (v.begin(), v.end(), [&](shop a, shop b) { return a.x < b.x; });

	for (int i = 0; i < v.size (); i++) {
		ans[i] = t_left.get (0, v[i].x) - D * v[i].x + v[i].m;
		ans[i] = max (ans[i], t_right.get (v[i].x, maxx) + U * v[i].x + v[i].m);
	}

	ans_l[0] = ans[0], ans_r.back() = ans.back();

	for (int i = 1; i < v.size (); i++) {
		ans_l[i] = max (ans[i], ans_l[i-1] - D * (v[i].x - v[i-1].x) + v[i].m);
	}

	for (int i = v.size () - 2; i >= 0; i--) {
		ans_r[i] = max (ans[i], ans_r[i+1] - U * (v[i+1].x - v[i].x) + v[i].m);
	}

	for (int i = 0; i < v.size (); i++) {
		ans[i] = max (ans_l[i], ans[i]);
		ans[i] = max (ans_r[i], ans[i]);

		//cout << v[i].x << ' ' << v[i].t << ' ' << ans[i] << endl;

		t_left.update (v[i].x, ans[i] + v[i].x * D);
		t_right.update (v[i].x, ans[i] - v[i].x * U);
	}
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> U >> D >> s;

	for (int i = 0; i < n; i++) {
		cin >> a[i].t >> a[i].x >> a[i].m;
		maxx = max (maxx, a[i].x);
	}

	t_left.build (maxx + 1);
	t_right.build (maxx + 1);

	t_right.update (s, -s * U);
	t_left.update (s, s * D);

	sort (a, a + n);

	int last = 0;

	for (int i = 0; i < n; i++) {
		if (a[i].t != a[last].t) {
			process (last, i);
			last = i;
		}
	}

	process (last, n);

	int ans = t_right.get (s, maxx) + U * s;
	ans = max (ans, t_left.get (0, s) - D * s);
	assert (ans >= 0);
	cout << ans;
}

Compilation message (stderr)

salesman.cpp: In function 'void process(int, int)':
salesman.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<shop>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (int i = 0; i < v.size (); i++) {
      |                  ~~^~~~~~~~~~~
salesman.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<shop>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 1; i < v.size (); i++) {
      |                  ~~^~~~~~~~~~~
salesman.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<shop>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = 0; i < v.size (); i++) {
      |                  ~~^~~~~~~~~~~

• Subtask 1: 98 / 100