제출 #335889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335889		sumit_kk10	쌀 창고 (IOI11_ricehub)	C++14	100 / 100	63 ms	3308 KiB

ricehub

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
 
long long int besthub(int n, int l, int a[], long long int b){
	long long int pre_sum[n] = {0}, suf_sum[n] = {0}, ans = 1;
	pre_sum[0] = a[0];
	suf_sum[n - 1] = a[n - 1];
	for(int i = 1; i < n; ++i)
		pre_sum[i] = pre_sum[i - 1] + a[i];
	for(int i = n - 2; i >= 0; --i)
		suf_sum[i] = suf_sum[i + 1] + a[i];
	for(int left = 0; left < n; ++left){
		int low = left + 1, high = n - 1;
		while(low <= high){
			int right = (low + high) / 2;
			long long int middle = (left + right) / 2;
			long long int val = pre_sum[right] - pre_sum[middle], val1 = suf_sum[left] - suf_sum[middle];
			val -= (a[middle] * (right - middle));
			val1 -= (a[middle] * (middle - left));
			val = abs(val), val1 = abs(val1);
			val += val1;
			// cout << left << ' ' << right << ' ' << middle << ' ' << val << '\n';
			if(val <= b){
				ans = max(ans, (long long int) right - left + 1);
				low  = right + 1;
			}
			else
				high = right - 1;
		}
	}
	return ans;
}

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