Submission #753716

#	Time	Username	Problem	Language	Result	Execution time	Memory
753716		nicksms	Rice Hub (IOI11_ricehub)	C++17	100 / 100	17 ms	3324 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

int besthub(int R, int L, int X[], ll B) {
	vl pre(R+1);
	vl x(R);
	for (int i = 0; i < R; i++) pre[i+1] = pre[i] + (x[i]=X[i]);
	int best = 1;
	int l = 0, r = 1;
	while (l < R) {
		r = max(l+1, r);
		while (r <= R) {
			int m = (l+r)/2;
			ll lo = pre[m]-pre[l];
			ll up = pre[r]-pre[m];
			lo = x[m]*(m-l) - lo;
			up -= x[m]*(r-m);
			if (lo + up <= B) {
				best = max(best, r-l);
				r += 1;
			} else break;
		}
		l++;
	}
	return best;
}

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