oj.uz

Submission #366930

# Submission time Handle Problem Language Result Execution time Memory
366930 2021-02-15T18:36:15 Z kostia244 Salesman (IOI09_salesman) C++17
100 / 100
 967 ms 43500 KB 
#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 = long long;
const ll inf = 1ll<<60;
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]+1) - 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];
		}
		
		vector<ll> dp_u;
		for(int i = 0; i < n; i++) {
			ll curv = up.query(0, cur[day][i][0]+1) - cur[day][i][0]*u;
			if(i) curv = max(curv, dp_u.back() - u*(cur[day][i][0]-cur[day][i-1][0]));
			dp_u.push_back(curv + cur[day][i][1]);
		}
		vector<ll> dp_d;
		for(int i = n; i--;) {
			ll curv = down.query(cur[day][i][0], maxn) + cur[day][i][0]*d;
			if(n-1-i) curv = max(curv, dp_d.back() - d*(cur[day][i+1][0]-cur[day][i][0]));
			dp_d.push_back(curv + cur[day][i][1]);
		}
		reverse(all(dp_d));
		for(int i = 0; i < n; i++) {
			upd(cur[day][i][0], max({dp_down[i], dp_up[i], dp_u[i], dp_d[i]}));
		}
	}
	ll res = max(up.query(0, s) - u*s, down.query(s, maxn) + d*s);
	cout << res << '\n';
}

Compilation message

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<long long 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27756 KB Output is correct
2 Correct 19 ms 27756 KB Output is correct
3 Correct 20 ms 27756 KB Output is correct
4 Correct 21 ms 27756 KB Output is correct
5 Correct 24 ms 28012 KB Output is correct
6 Correct 52 ms 28396 KB Output is correct
7 Correct 112 ms 29420 KB Output is correct
8 Correct 207 ms 30828 KB Output is correct
9 Correct 294 ms 32436 KB Output is correct
10 Correct 433 ms 37100 KB Output is correct
11 Correct 601 ms 37192 KB Output is correct
12 Correct 719 ms 40320 KB Output is correct
13 Correct 744 ms 40428 KB Output is correct
14 Correct 967 ms 43500 KB Output is correct
15 Correct 732 ms 43500 KB Output is correct
16 Correct 960 ms 43500 KB Output is correct
17 Correct 19 ms 27756 KB Output is correct
18 Correct 19 ms 27756 KB Output is correct
19 Correct 21 ms 27756 KB Output is correct
20 Correct 24 ms 27756 KB Output is correct
21 Correct 21 ms 27756 KB Output is correct
22 Correct 24 ms 27884 KB Output is correct
23 Correct 23 ms 27884 KB Output is correct
24 Correct 24 ms 27884 KB Output is correct
25 Correct 149 ms 29036 KB Output is correct
26 Correct 260 ms 30956 KB Output is correct
27 Correct 458 ms 34204 KB Output is correct
28 Correct 488 ms 33208 KB Output is correct
29 Correct 682 ms 33028 KB Output is correct
30 Correct 621 ms 36268 KB Output is correct