Submission #319212

#	Time	Username	Problem	Language	Result	Execution time	Memory
319212		sofapuden	Rice Hub (IOI11_ricehub)	C++14	100 / 100	20 ms	2596 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int besthub(int R, int L, int* X, ll B){
	ll sum, a[R];
	a[0] = X[0];
	for(int i = 1; i < R; ++i)a[i] = a[i-1]+X[i];
	
	int x = 0, ans = 0;
	for(int j = 0; j < R; ++j){
		ll mid = (x+j)>>1;
		sum = ((mid-x+1) - (j-mid))*X[mid]-(a[mid]-(x?a[x-1]:0))+(a[j]-a[mid]);
		while(sum > B){
			++x;
			mid = (x+j)>>1;
			sum = ((mid-x+1) - (j-mid))*X[mid]-(a[mid]-(x?a[x-1]:0))+(a[j]-a[mid]);
		}
		ans = max(ans, j-x+1);
	}
	return ans;
}

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