Submission #1250114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250114		Nurislam	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	324 KiB

ricehub

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

using namespace std;
typedef long long ll;

ll inf = 1e18;

int besthub(int n, int L, int A[], ll b){
	vector<ll> a(n);
	for(int i = 0; i < n; i ++ ) a[i] = A[i];
	sort(a.begin(), a.end());
	a.push_back(a.back());
	ll ans = 0;
	
	
	ll cur = 0;
	ll l = 0, r = 0;
	
	for(int i = 0; i < n; i ++ ) {
		if(r < i)r++;
		while(cur > b && l < i) {
			cur -= a[i] - a[l];
			l++;
		};
		
		while(r+1 < n && a[i] - a[l] > a[r+1] - a[i]){
			r ++;
			cur += a[r] - a[i];
			cur += a[i] - a[l];
			l ++;
		};
		
		
		while(1) {
			ll lf = (l== 0 ? inf: a[i] - a[l-1]);
			ll ri = (r==n-1 ? inf: a[r+1] - a[i]);
			if(lf == inf && ri == inf) break;
			if(lf <= ri && lf + cur <= b) {
				cur += lf;l -- ;
			}else if(ri < lf && ri + cur <= b) {
				cur += ri;r ++ ;
			}else break;
		};
		
		ans = max(ans, r-l+1);
		
		cur += ((i-l+1) - (r - i)) * (a[i+1]-a[i]);
	};
	
	return ans;
}

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