Submission #366912

#	Time	Username	Problem	Language	Result	Execution time	Memory
366912		kostia244	Salesman (IOI09_salesman)	C++17	0 / 100	730 ms	44652 KiB

salesman

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn =5e5 + 15, C = 1;
using ll = int;
const ll inf = 1ll<<55;
struct segtree {
	vector<ll> t;
	int n;
	segtree(int n) : n(n), t(2*n, -inf) {}
	void update(int pos, ll val) {
		t[pos+n] = max(t[pos+n], val);
		for(pos+=n;pos/=2;) t[pos] = max(t[2*pos], t[2*pos+1]);
	}
	ll query(int l, int r) {
		ll ans = -inf;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
			if(l&1) ans = max(ans, t[l++]);
			if(r&1) ans = max(ans, t[--r]);
		}
		return ans;
	}
};
int n, s;
ll u, d;
segtree down(maxn), up(maxn);
vector<array<int, 2>> cur[maxn];
void upd(int pos, ll val) {
	down.update(pos, val - d*pos);
	up.update(pos, val + u*pos);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> d >> u >> s;
	upd(s, 0);
	for(int d, l, c, i = 0; i < n; i++) {
		cin >> d >> l >> c;
		cur[d].push_back({l, c});
	}
	for(int day = 0; day < maxn; day++) if(!cur[day].empty()) {
		n = cur[day].size();
		sort(all(cur[day]));
		vector<ll> dp_down(n), dp_up(n);
		for(int i = 0; i < n; i++) {
			dp_down[i] = max(-inf, down.query(cur[day][i][0], maxn) + cur[day][i][0]*d);
		}
		for(int i = 0; i < n; i++) {
			if(i) dp_down[i] = max(dp_down[i], dp_down[i-1] - u*(cur[day][i][0]-cur[day][i-1][0]));
			dp_down[i] += cur[day][i][1];
		}
		for(int i = 0; i < n; i++) {
			dp_up[i] = max(-inf, up.query(0, cur[day][i][0]) - cur[day][i][0]*u);
		}
		for(int i = n; i--;) {
			if(i+1<n) dp_up[i] = max(dp_up[i], dp_up[i+1] - d*(cur[day][i+1][0]-cur[day][i][0]));
			dp_up[i] += cur[day][i][1];
		}
		
		for(int i = 0; i < n; i++) {
			upd(cur[day][i][0], max(dp_down[i], dp_up[i]));
		}
	}
	ll res = max(up.query(0, s) - u*s, down.query(s, maxn) + d*s);
	cout << res << '\n';
}

Compilation message (stderr)

salesman.cpp:8:19: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '36028797018963968' to '0' [-Woverflow]
    8 | const ll inf = 1ll<<55;
      |                ~~~^~~~
salesman.cpp: In constructor 'segtree::segtree(int)':
salesman.cpp:11:6: warning: 'segtree::n' will be initialized after [-Wreorder]
   11 |  int n;
      |      ^
salesman.cpp:10:13: warning:   'std::vector<int> segtree::t' [-Wreorder]
   10 |  vector<ll> t;
      |             ^
salesman.cpp:12:2: warning:   when initialized here [-Wreorder]
   12 |  segtree(int n) : n(n), t(2*n, -inf) {}
      |  ^~~~~~~

• Subtask 1: 0 / 100