oj.uz

Submission #473461

# Submission time Handle Problem Language Result Execution time Memory
473461 2021-09-15T14:39:25 Z hhhhaura Rice Hub (IOI11_ricehub) C++14
100 / 100
 348 ms 3328 KB 
#define wiwihorz
#include "ricehub.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
 
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
 
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
 
using namespace std;
 
#define ll long long int
#define lld long double
#define pii pair<ll, ll> 
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

ll n;
vector<ll> a, pre;
pii get_val(ll x, ll len) {
	ll L, R, ans = 0, cnt = 0;
	L = 0, R = x;
	while(R - L > 1) {
		int mid = (L + R) / 2;
		if(a[x] - a[mid] <= len) R = mid;
		else L = mid;
	}
	cnt += x - R + 1;
	ans += a[x] * (x - R + 1) - (pre[x] - pre[R - 1]);
	L = x, R = n + 1;
	while(R - L > 1) {
		int mid = (L + R) / 2;
		if(a[mid] - a[x] <= len) L = mid;
		else R = mid;
	}
	cnt += L - x;
	ans += pre[L] - pre[x] - (L - x) * a[x];
	return {cnt, ans};
}
int besthub(int R, int L, int X[], ll B) {
	n = R;
	a.assign(R + 1, 0);
	pre.assign(R + 1, 0);
	rep(i, 1, R) {
		a[i] = X[i - 1];
		pre[i] = pre[i - 1] + X[i - 1];
	}
	ll ans = 0; 
	rep(i, 1, R) {
		ll l = 0, r = L;
		ll cost = 0, cnt = 0, val = 0, val2 = 0, cc = 0;
		while(r - l > 1) {
			int mid = (l + r) / 2;
			if(tie(cnt, cost) = get_val(i, mid), 
				cost <= B) val = cnt, l = mid, cc = cost;
			else r = mid, val2 = cnt; 
		}
		val2 = get_val(i, r).first;
		ans = max(ans, val + min((B - cc) / r, val2 - val));
	}
	return ans;
}

Compilation message

ricehub.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      |

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 208 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 2 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 7 ms 332 KB Output is correct
22 Correct 8 ms 396 KB Output is correct
23 Correct 5 ms 396 KB Output is correct
24 Correct 9 ms 332 KB Output is correct
25 Correct 10 ms 332 KB Output is correct
26 Correct 9 ms 400 KB Output is correct
27 Correct 10 ms 332 KB Output is correct
28 Correct 10 ms 332 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 588 KB Output is correct
2 Correct 32 ms 588 KB Output is correct
3 Correct 252 ms 2256 KB Output is correct
4 Correct 317 ms 2308 KB Output is correct
5 Correct 135 ms 1280 KB Output is correct
6 Correct 120 ms 1620 KB Output is correct
7 Correct 175 ms 3036 KB Output is correct
8 Correct 205 ms 3020 KB Output is correct
9 Correct 105 ms 1564 KB Output is correct
10 Correct 120 ms 1556 KB Output is correct
11 Correct 265 ms 3328 KB Output is correct
12 Correct 348 ms 3324 KB Output is correct
13 Correct 134 ms 1668 KB Output is correct
14 Correct 134 ms 1596 KB Output is correct
15 Correct 166 ms 2552 KB Output is correct
16 Correct 228 ms 2508 KB Output is correct
17 Correct 210 ms 2944 KB Output is correct
18 Correct 288 ms 2988 KB Output is correct
19 Correct 214 ms 3160 KB Output is correct
20 Correct 310 ms 3164 KB Output is correct