제출 #330612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330612		MetB	Salesman (IOI09_salesman)	C++14	98 / 100	565 ms	32672 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;

ll n, U, D, s, maxx;

struct SegTree {
	ll t[N], start;

	void build (ll n) {
		start = 1;
		while (start < n) start <<= 1;
		fill (t, t + 2 * start, -INF);
	}

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

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

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

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

		ll mx = -INF;

		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 {
	ll x, t, m;

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

void process (ll l, ll r) {

	vector <shop> v (a + l, a + r);
	vector <ll> 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 (ll 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 (ll 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 (ll 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 (ll 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 (ll 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);

	ll last = 0;

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

	process (last, n);

	ll ans = t_right.get (s, maxx) + U * s;
	ans = max (ans, t_left.get (0, s) - D * s);

	cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 98 / 100