oj.uz

Submission #478861

# Submission time Handle Problem Language Result Execution time Memory
478861 2021-10-08T16:04:12 Z nicetrymaza Rice Hub (IOI11_ricehub) C++14
68 / 100
 16 ms 3372 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define add push_back
#define mp make_pair
#define fr first
#define sc second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define filein(a) freopen(a, "r", stdin);
#define fileout(a) freopen(a, "w", stdout);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
 
const int N = 100011;
const ll MOD = 1000000007;
 
int besthub(int R, int L, int X[], ll B) {
	if(R == 1) return 1;
	ll a[N], b[N];
	a[0] = 0;
	b[R + 1] = 0;
	for(int i = 1; i <= R; i++) {
		if(i == 1) a[i] = 0;
		else a[i] = a[i - 1] + (i - 1) * (X[i - 1] - X[i - 2]);
	}
 
	for(int i = R; i >= 1; i--) {
		if(i == R) b[i] = 0;
		else b[i] = b[i + 1] + (R - i) * (X[i] - X[i - 1]);
	}
	int l = 1, r = R, ans = 1;
	while(l <= r) {
		bool yes = true;
		int m = (l + r) / 2;
		int mi = m / 2, mj = (m + 1) / 2;
		for(int i = mi; (i + mj) < R; i++) {
			if(i == 0) {
				if(B >= (X[i + 1] - X[i])) {
					ans = 2;
					l = m + 1;
					i = R;
					yes = false;
				}
			}
			else {
				ll c1 = a[i + 1] - a[i - mi + 1] - (i - mi) * (X[i] - X[i - mi]);
				ll c2 = b[i + 1] - b[i + 1 + mj] - (R - i - 1 - mj) * (X[i + mj] - X[i]);
				if((c1 + c2) <= B) {
					ans = m + 1;
					l = m + 1;
					i = R;
					yes = false;
				}
			}
		}
		if(yes) r = m - 1;
	}
	return ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1908 KB Output is correct
2 Correct 5 ms 1996 KB Output is correct
3 Correct 14 ms 3272 KB Output is correct
4 Correct 16 ms 3320 KB Output is correct
5 Correct 8 ms 2380 KB Output is correct
6 Correct 9 ms 2380 KB Output is correct
7 Correct 14 ms 3020 KB Output is correct
8 Correct 12 ms 3020 KB Output is correct
9 Correct 9 ms 2252 KB Output is correct
10 Correct 9 ms 2252 KB Output is correct
11 Correct 14 ms 3372 KB Output is correct
12 Incorrect 15 ms 3276 KB Output isn't correct
13 Halted 0 ms 0 KB -