Submission #97396

#	Time	Username	Problem	Language	Result	Execution time	Memory
97396		Shafin666	Rice Hub (IOI11_ricehub)	C++14	100 / 100	24 ms	3200 KiB

ricehub

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>
#define to second
#define cost first
typedef long long ll;
typedef long double ld;
using namespace std;

ll a[1000005];
ll l[1000005];

bool can(int i, int j, ll b) {
	int mid = (i+j)/2;

	ll left = (mid-i+1)*a[mid] - (l[mid]-l[i-1]);
	ll right = l[j]-l[mid-1] - (j-mid+1)*a[mid];
	return left+right <= b;
}

ll besthub(int r, int L, int x[], ll b) {
	int maxlen = -1;

	for(int i = 0; i < r; i++) a[i+1] = x[i];
	for(int i = 1; i <= r; i++) l[i] = l[i-1] + a[i];

	int ptr = 1;
	for(int i = 1; i <= r; i++) {
		ptr = max(i, ptr);
		while(ptr+1 <= r && can(i, ptr+1, b)) ptr++;
		maxlen = max(maxlen, ptr-i+1);
	}

	return maxlen;
}
/*
int main()
{	
	int x[1] = {1};
	cout << besthub(1, 20, x, 6) << endl;

    return 0;
}*/

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32