Submission #1128285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128285		ChuanChen	Rice Hub (IOI11_ricehub)	C++20	100 / 100	11 ms	2376 KiB

ricehub

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

using namespace std;

const int lim = 1e5+5;
typedef long long ll;

ll bucket, sv[lim], x[lim];
int ans;

bool valid(int l, int r){
	int mid = (l+r)/2;
	ll cost = sv[r]-sv[mid] - (r-mid)*x[mid] + (mid-l)*x[mid] - (sv[mid-1]-sv[l-1]);

	return cost <= bucket;
}

int besthub(int R, int L, int X[], long long B){
	bucket = B;
	for(int i = 1; i <= R; i++){
		x[i] = X[i-1];
		sv[i] = sv[i-1] + x[i];
	}

	int r = 1;
	for(int l = 1; l <= R; l++){

		while(r <= R && valid(l, r)){
			ans = max(r-l+1, ans);
			r++;
		}
	}

	return ans;
}

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