Submission #655640

#	Time	Username	Problem	Language	Result	Execution time	Memory
655640		horiseun	Rice Hub (IOI11_ricehub)	C++11	100 / 100	16 ms	1868 KiB

ricehub

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
#define ll long long

vector<ll> pref;
 
ll calc(int length, int x[], int r) {
	ll val = LLONG_MAX;
	for (int i = length - 1; i < r; i++) {
		int start = i - length + 1;
		int pos = (i + i - length + 1) / 2;
		val = min(val, (pos - start) * x[pos] - (pref[pos] - pref[start]) + (pref[i + 1] - pref[pos + 1]) - (i - pos) * x[pos]);
	}
	return val;
}
 
int besthub(int r, int l, int x[], ll b) {
	pref.push_back(0);
	for (int i = 0; i < r; i++) {
		pref.push_back(pref[i] + x[i]);
	}
 
	int low = 0, upp = r + 1;
	while (low + 1 != upp) {
		int mid = (low + upp) / 2;
		if (calc(mid, x, r) <= b) low = mid;
		else upp = mid;
	}
    return low;
}

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