Submission #953921

#	Time	Username	Problem	Language	Result	Execution time	Memory
953921		4QT0R	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	3752 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll pref[100003];
ll pos[100003];

ll cost(ll l, ll p){
	ll med=(l+p)/2;
	return pref[p]-2*pref[med]+pref[l-1]+(!((l+p)&1))*pos[med];
}

ll besthub(int n, int L, int x[], ll bud){
	for (ll i = 0; i<n; i++){
		pos[i+1]=x[i];
		pref[i+1]=pref[i]+(ll)x[i];
	}
	ll mx=1,p=1;
	for (ll l = 1; l<=n; l++){
		while(p<n && cost(l,p+1)<=bud)p++;
		mx=max(mx,p-l+1);
	}
	return mx;
}

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