Submission #60130

#	Time	Username	Problem	Language	Result	Execution time	Memory
60130		streifi	Rice Hub (IOI11_ricehub)	C++14	0 / 100	8 ms	1592 KiB

ricehub

#include <iostream>
#include <vector>
using namespace std;

#define int long long

int R, L, B;
vector<int> lft, rght;
vector<int> v;

bool check(int sz) {
	for (int l = 0; l+sz-1 < R; ++l) {
		int r = l+sz-1;
		int med = (l+r)/2;
		//cout << l << " " << med << " " << r << endl;
		//cout << lft[r+1]-lft[med+1] << " " << rght[l+1]-rght[med+1] << endl;
		int cur = lft[r+1]-lft[med+1]-(r-med)*v[med] + rght[l+1]-rght[med+1]-(med-l)*(L-v[med]);
		//cout << cur << endl;
		if (cur <= B)
			return true;
	}
	return false;
}

int besthub(signed r, signed l, signed *nv, long long b) {
	R = r, L = l, B = b;
	for (int i = 0; i < R; ++i) {
		v.push_back(nv[i]);
	}
	for (int i = 1; i <= R; ++i) {
		lft[i] = lft[i-1]+v[i-1];
	}
	for (int i = R; i >= 1; --i) {
		rght[i] = rght[i+1]+(L-v[i-1]);
	}

	int ans = 0;
	for (int msk = (1 << 20); msk > 0; msk >>= 1) {
		if ((ans | msk) <= R && check(ans | msk)) {
			ans |= msk;
		}
	}

	return ans;
}

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