Submission #1127214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127214		freedommo33	Rice Hub (IOI11_ricehub)	C++20	100 / 100	12 ms	2376 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M = 100'005;
ll tab[M];
ll pref[M];

ll suma(int l, int r){
	return pref[r] - pref[l-1];
}

int besthub(int n, int L, int X[], long long B){
	for(int i=1; i<=n; i++) tab[i] = X[i-1];
	for(int i=1; i<=n; i++) pref[i]  =  pref[i-1] + tab[i];
	
	ll l = 1;
	ll wynik = 0;
	for(ll r=1; r<=n; r++){
		int mid = (l + r) / 2;
		ll koszt = tab[mid] * (mid - l + 1) - suma(l+1, mid) - tab[l];
		koszt += suma(mid+1, r) - tab[mid] * (r - mid);
		while(l < r && koszt > B){
			l++;
			koszt = tab[mid] * (mid - l + 1) - suma(l+1, mid) - tab[l];
			koszt += suma(mid+1, r) - tab[mid] * (r - mid);
		}
		wynik = max(wynik, r - l + 1);
	}
	return wynik;
}

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