Submission #102972

#	Time	Username	Problem	Language	Result	Execution time	Memory
102972		hugo_pm	Rice Hub (IOI11_ricehub)	C++17	100 / 100	32 ms	1920 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long llg;

int besthub(int R, int L, int X[], long long B)
{
	int deb = 0, mid = 0, fin = 0;
	int rep = 1;
	llg cur = 0;
	while (fin+1 < R) {
		++fin;
		cur += (X[fin] - X[mid]);
		while (deb <= fin) {
			while (mid+1 <= fin) {
				llg delta = X[mid+1] - X[mid];
				llg gl = (mid-deb+1);
				llg gr = (fin-(mid+1)+1);
				assert(gl+gr == fin-deb+1);
				llg nc = cur + gl*delta - gr*delta;
				if (nc > cur) break;
				cur = nc;
				++mid;
			}
			if (cur <= B) {
				break;
			}
			cur -= (X[mid]-X[deb]);
			++deb;
		}
		rep = max(rep, fin-deb+1);
	}
	return rep;
}

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