제출 #54839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54839		ernestvw	쌀 창고 (IOI11_ricehub)	C++11	100 / 100	37 ms	4016 KiB

ricehub

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

#include "ricehub.h"

#define int long long

int prefix[100003], suffix[100003];
int r, l, pos[100003];
int b;

int costLeft(int x, int g, int d) {
	int dst = x - pos[d];
	dst *= (d - g + 1LL);
	dst += suffix[g] - suffix[d+1] - (l - pos[d]) * (d - g + 1LL);
	return dst;
}

int costRight(int x, int g, int d) {
	int dst = pos[g] - x;
	dst *= (d - g + 1LL);
	dst += prefix[d] - prefix[g-1] - pos[g] * (d - g + 1LL);
	return dst;
}

int cost(int g, int d) {
	int x = pos[(g + d) / 2];
	return costLeft(x, g, (g+d)/2) + costRight(x, (g+d)/2+1, d);
}

bool ok(int g, int d) {
	return cost(g, d) <= b;
}

int32_t besthub(int32_t R, int32_t L, int32_t *X, long long B) {
	for(int i = 1; i <= R; i++) pos[i] = X[i-1];
	r = R, l = L, b = B;
	prefix[0] = suffix[R+1] = 0;
	for(int i = 1; i <= R; i++)
		prefix[i] = prefix[i-1] + pos[i];
	for(int i = R; i >= 1; i--)
		suffix[i] = suffix[i+1] + l - pos[i];
	int ans = 1;
	int j = -1;
	for(int i = 1; i <= R; i++) {
		if(j < i) {
			j = i;
		}
		ans = max(ans, j-i+1);
		while(j+1 <= R and ok(i, j+1)) {
			ans = max(ans, (j+1-i+1));
			j++;
		}
	}
	return ans;
}

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