Submission #172727

#	Time	Username	Problem	Language	Result	Execution time	Memory
172727		maximath_1	Rice Hub (IOI11_ricehub)	C++11	100 / 100	20 ms	2556 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll cnt[100005];
bool check(int n, int pos, ll lim){
	int l, r, md;
	ll rs;
	for(int i=1; i<=n-pos+1; i++){
		l=i; r=i+pos-1;
		md=(l+r)>>1;
		rs=(cnt[r]-cnt[md])-(cnt[md-pos%2]-cnt[l-1]);
		if(rs<=lim) return true;
	}
	return false;
}
int besthub(int R, int L, int* X, ll B){
	for(int i=1; i<=R; i++)
		cnt[i]=cnt[i-1]+X[i-1];
	int l=0, r=R;
	while(l!=r){
		int md=(l+r+1)>>1;
		if(check(R, md, B)) l=md;
		else r=md-1;
	}
	return l;
}

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