oj.uz

Submission #833003

# Submission time Handle Problem Language Result Execution time Memory
833003 2023-08-21T18:53:44 Z Halym2007 Rice Hub (IOI11_ricehub) C++11
100 / 100
 12 ms 4140 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int besthub(int R, int L, int X[], ll B) {
	vector <ll> arr(R + 1, 0), p(R + 1, 0), pr(R + 2, 0);
	for (int i = 0; i < R; ++i) {
		arr[i + 1] = X[i];
	}
	for (ll i = 1; i <= R; ++i) {
		p[i] = (arr[i] - arr[i - 1]) * (i - 1) + p[i - 1];
	}
	
	for (ll i = R; i > 0; i--) {
		pr[i] = (arr[i + 1] - arr[i]) * (R - i) + pr[i + 1];
	}
	ll l = 1, r = 1, jogap = 1;
	while (l <= R and r <= R) {
		ll md = (l + r + 1) / 2; 
		ll sum = p[md] - p[l - 1] - ((l - 1) * (arr[md] - arr[l - 1])); 
		ll sum1 = pr[md] - pr[r + 1] - ((R - r) * (arr[r + 1] - arr[md])); // yalnysh su
		ll sum2 = sum + sum1;
		if (sum2 <= B) {
			r++;
		}
		else {
			// l r -1 
			jogap = max (jogap, r - l);
			l++;
		}
	}
	jogap = max (jogap, r - l);
	return jogap;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 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 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 452 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 452 KB Output is correct
25 Correct 1 ms 448 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 480 KB Output is correct
28 Correct 1 ms 448 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 988 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 11 ms 4088 KB Output is correct
4 Correct 12 ms 4052 KB Output is correct
5 Correct 6 ms 1980 KB Output is correct
6 Correct 6 ms 2004 KB Output is correct
7 Correct 9 ms 3812 KB Output is correct
8 Correct 11 ms 3796 KB Output is correct
9 Correct 5 ms 1876 KB Output is correct
10 Correct 5 ms 1956 KB Output is correct
11 Correct 10 ms 4140 KB Output is correct
12 Correct 12 ms 4044 KB Output is correct
13 Correct 5 ms 1976 KB Output is correct
14 Correct 5 ms 2004 KB Output is correct
15 Correct 9 ms 3076 KB Output is correct
16 Correct 8 ms 3068 KB Output is correct
17 Correct 11 ms 3636 KB Output is correct
18 Correct 9 ms 3600 KB Output is correct
19 Correct 11 ms 3924 KB Output is correct
20 Correct 10 ms 3932 KB Output is correct