제출 #311352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311352		LucaDantas	쌀 창고 (IOI11_ricehub)	C++17	100 / 100	26 ms	2432 KiB

ricehub

#include "ricehub.h"
#include<algorithm>
#include<cstdio>
#include <cassert>

using ll = long long;

constexpr int maxn = 1e5+10;

ll pref[maxn];

inline ll itv(int l, int r) { return pref[r] - (l?pref[l-1]:0); }

ll cost(int l, int r, int a[]) {
	if(l == r) return 0;
	int m = (l+r) >> 1;
	int pos = a[m];
	ll cost = 1ll*pos*(m-l+1) - itv(l, m);
	cost += itv(m+1, r) - 1ll*pos*(r-m);
	return cost;
}

int besthub(int n, int l, int a[], ll b)
{
	int ans = 0;
	pref[0] = a[0];
	for(int i = 1; i < n; i++)
		pref[i] = pref[i-1]+a[i];
	for(int i = 0; i < n; i++) {
		int l = i, r = n-1, best = -1;
		while(l <= r) {
			int m = (l+r) >> 1;
			if(cost(i, m, a) <= b)
				best = m, l = m+1;
			else
				r = m-1;
		}
		// printf("%d %d\n", i, best);
		assert(best != -1);
		ans = std::max(ans, best - i + 1);
	}
	return ans;
}

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