제출 #583651

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

ricehub

#include "ricehub.h"
#include <iostream>
#include <vector>

#define int long long
using namespace std;
int32_t besthub(int32_t R, int32_t L, int32_t X[], long long B)
{
	int n = R;

	vector<int> dpSum(n + 1);
	for (int i = 1; i <= n; i++) {
		dpSum[i] = dpSum[i - 1] + X[i - 1];
	}

	auto rangeSum = [=](int a, int b) -> int {
		return dpSum[b + 1] - dpSum[a];
	};

	auto cost = [=](int from, int to) -> int {
		int median = (from + to) / 2;
		int leftN = median - from;
		int leftSum = rangeSum(from, median - 1);

		int rightN = to - median;
		int rightSum = rangeSum(median + 1, to);

		int currCost = (X[median] * leftN - leftSum) + (rightSum - X[median] * rightN);

		return currCost;
	};

	int from = 0;
	int to = 0;
	int res = 1;

	while (true) {
		to++;
		if (to >= n) break;
		int currCost = cost(from, to);
		if (currCost > B) from++;
		else res = max(res, to - from + 1);
	}
	
	return res;

}

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