Submission #80576

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80576	2018-10-21T13:07:14 Z	arman_ferdous	Rice Hub (IOI11_ricehub)	C++17	17 / 100	82 ms	2696 KB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;

typedef long long ll;
const int N = 1e5+10;
int n; ll arr[N], sum[N], cap, lim;

ll calc(ll i, ll j, ll x) {
	ll p = lower_bound(arr,arr+n,x) - arr; p++;
	ll ret = x * (p - i) - (sum[p-1] - sum[i-1]);
	ret = ret + sum[j] - sum[p-1] - x * (j - p + 1);
	return ret;
}

bool ok(int l, int r) {
	ll med = (sum[r] - sum[l-1]) / (r - l + 1);
	for(ll i = max(0ll,med - 10); i <= min(med+10,lim); i++)
		if(calc(l,r,i) <= cap) return true;
	return false;
}

int besthub(int R, int L, int X[], ll B) {
	n = R, cap = B, lim = L; sum[0] = 0;
	for(int i = 0; i < R; i++) arr[i] = X[i];
	for(int i = 1; i <= R; i++) sum[i] = sum[i-1] + X[i-1];

	int r = 1, ans = 0;
	for(int l = 1; l <= n; l++) {
		while(r + 1 <= n && ok(l,r+1)) ++r;
		if(ok(l,r)) ans = max(ans, r - l + 1);
	}
	return ans;
}

Subtask #1

17.0 / 17.0

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

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	508 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	552 KB	Output is correct
4	Correct	2 ms	552 KB	Output is correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	2 ms	692 KB	Output is correct
8	Correct	3 ms	692 KB	Output is correct
9	Correct	2 ms	692 KB	Output is correct
10	Correct	2 ms	692 KB	Output is correct
11	Correct	2 ms	692 KB	Output is correct
12	Correct	2 ms	692 KB	Output is correct
13	Correct	2 ms	692 KB	Output is correct
14	Correct	2 ms	692 KB	Output is correct
15	Correct	2 ms	692 KB	Output is correct
16	Correct	2 ms	692 KB	Output is correct
17	Correct	2 ms	692 KB	Output is correct
18	Correct	2 ms	692 KB	Output is correct
19	Correct	2 ms	692 KB	Output is correct
20	Correct	2 ms	692 KB	Output is correct
21	Correct	2 ms	692 KB	Output is correct
22	Correct	2 ms	692 KB	Output is correct
23	Correct	2 ms	692 KB	Output is correct
24	Correct	2 ms	692 KB	Output is correct
25	Correct	2 ms	692 KB	Output is correct
26	Correct	3 ms	692 KB	Output is correct
27	Incorrect	2 ms	692 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #3

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	692 KB	Output is correct
2	Correct	3 ms	692 KB	Output is correct
3	Correct	3 ms	692 KB	Output is correct
4	Correct	2 ms	692 KB	Output is correct
5	Correct	2 ms	692 KB	Output is correct
6	Correct	3 ms	692 KB	Output is correct
7	Correct	3 ms	692 KB	Output is correct
8	Correct	3 ms	692 KB	Output is correct
9	Correct	3 ms	776 KB	Output is correct
10	Correct	3 ms	776 KB	Output is correct
11	Correct	3 ms	776 KB	Output is correct
12	Correct	3 ms	776 KB	Output is correct
13	Correct	2 ms	776 KB	Output is correct
14	Correct	2 ms	776 KB	Output is correct
15	Correct	2 ms	776 KB	Output is correct
16	Correct	2 ms	776 KB	Output is correct
17	Correct	2 ms	776 KB	Output is correct
18	Correct	2 ms	776 KB	Output is correct
19	Correct	2 ms	776 KB	Output is correct
20	Correct	3 ms	776 KB	Output is correct
21	Correct	10 ms	860 KB	Output is correct
22	Correct	9 ms	860 KB	Output is correct
23	Correct	3 ms	860 KB	Output is correct
24	Correct	3 ms	860 KB	Output is correct
25	Correct	3 ms	860 KB	Output is correct
26	Correct	3 ms	860 KB	Output is correct
27	Incorrect	5 ms	860 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1156 KB	Output is correct
2	Correct	24 ms	1156 KB	Output is correct
3	Correct	35 ms	2692 KB	Output is correct
4	Correct	33 ms	2692 KB	Output is correct
5	Correct	81 ms	2692 KB	Output is correct
6	Correct	82 ms	2692 KB	Output is correct
7	Correct	26 ms	2692 KB	Output is correct
8	Correct	25 ms	2692 KB	Output is correct
9	Correct	58 ms	2692 KB	Output is correct
10	Correct	49 ms	2692 KB	Output is correct
11	Correct	33 ms	2692 KB	Output is correct
12	Correct	33 ms	2696 KB	Output is correct
13	Correct	63 ms	2696 KB	Output is correct
14	Correct	59 ms	2696 KB	Output is correct
15	Correct	26 ms	2696 KB	Output is correct
16	Incorrect	27 ms	2696 KB	Output isn't correct
17	Halted	0 ms	0 KB	-