oj.uz

Submission #441447

# Submission time Handle Problem Language Result Execution time Memory
441447 2021-07-05T08:13:28 Z dutch Salesman (IOI09_salesman) C++17
100 / 100
 422 ms 19876 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p a[i][1]

const int INF = 1e18, H = 5e5+2;

void z(int &a, int b){ a = max(a, b); }

struct FenwickTree{
	vector<int> a; int n, i, f;
	FenwickTree(int N, bool flipped) : a((n=N)+1, -INF), f(flipped) {}
	FenwickTree& operator[](int j){ i = f ? n-j : j+1; return *this; }
	void operator=(int v){
		for(; i<=n; i+=i&-i) z(a[i], v);
	}
	int operator()(int j){
		i = f ? n-j : j+1; int s = -INF;
		for(; i>=1; i-=i&-i) z(s, a[i]);
		return s;
	}
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	int n, u, d, s; cin >> n >> u >> d >> s;
	d = -d, u = -u;
	array<int, 3> a[n]; // day, location, profitability
	for(auto &i : a){
		cin >> i[0] >> i[1] >> i[2];
	}
	sort(a, a+n);

	FenwickTree dpD(H, 1), dpU(H, 0);
	dpD[s] = s * d, dpU[s] = - s * u;

	for(int l=0; l<n; ){
		int r = l+1;
		while(r<n && a[l][0] == a[r][0]) ++r;

		for(int i=l; i<r; ++i){
			a[i][0] = -INF;
			z(a[i][0], dpD(p) - p * d);
			z(a[i][0], p * u + dpU(p));
		}

		int pre = -INF, suf = -INF, sum = 0;

		for(int i=l; i<r; ++i){
			z(pre, a[i][0] - p * u - sum);
			sum += a[i][2];
			dpD[p] = (pre + sum + p * u) + p * d;
			dpU[p] = (pre + sum + p * u) - p * u;
		}

		sum = 0;

		for(int i=r-1; i>=l; --i){
			z(suf, a[i][0] + p * d - sum);
			sum += a[i][2];
			dpD[p] = (suf + sum - p * d) + p * d;
			dpU[p] = (suf + sum - p * d) - p * u;
		}

		l = r;
	}

	int ans = 0;
	ans = max(ans, dpD(s) - s * d);
	ans = max(ans, dpU(s) + s * u);
	cout << ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 7 ms 8140 KB Output is correct
6 Correct 21 ms 8584 KB Output is correct
7 Correct 49 ms 9308 KB Output is correct
8 Correct 92 ms 10444 KB Output is correct
9 Correct 127 ms 11716 KB Output is correct
10 Correct 220 ms 15180 KB Output is correct
11 Correct 254 ms 15172 KB Output is correct
12 Correct 354 ms 17492 KB Output is correct
13 Correct 309 ms 17476 KB Output is correct
14 Correct 389 ms 19844 KB Output is correct
15 Correct 352 ms 19840 KB Output is correct
16 Correct 417 ms 19876 KB Output is correct
17 Correct 4 ms 8140 KB Output is correct
18 Correct 4 ms 8140 KB Output is correct
19 Correct 5 ms 8140 KB Output is correct
20 Correct 6 ms 8140 KB Output is correct
21 Correct 6 ms 8140 KB Output is correct
22 Correct 8 ms 8236 KB Output is correct
23 Correct 7 ms 8268 KB Output is correct
24 Correct 7 ms 8148 KB Output is correct
25 Correct 84 ms 10448 KB Output is correct
26 Correct 176 ms 12800 KB Output is correct
27 Correct 284 ms 16324 KB Output is correct
28 Correct 272 ms 16332 KB Output is correct
29 Correct 422 ms 19836 KB Output is correct
30 Correct 390 ms 19844 KB Output is correct