제출 #307996

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

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], n;
long long b;
bool check(int cnt){
	//two pointers?
	if(cnt == 1){
		return true;
	}
	int l=0, r=cnt-1;
	long long suml = 0, sumr = 0;
	long long m = a[(cnt-1)/2];
	for(int i=0; i<cnt/2; i++)suml += m-a[i];
	for(int i=cnt/2;i<cnt;i++)sumr += a[i]-m;
	
	bool flag = false;
	while(true){
	//	cout << suml << ' ' << sumr << '\n';
		if(b >= suml + sumr)flag = true;
		
		l++, r++;
		int median = l + (cnt-1)/2;
		if(r >= n)break;
		suml -= a[median-1]-a[l-1];
		suml += ((cnt-1)/2)*(a[median]-a[median-1]);
		sumr -= ((cnt)/2)*(a[median]-a[median-1]);
		sumr += a[r]-a[median];
	}
	return flag;
}
int besthub(int R, int L, int X[], long long B){
	n = R;
	b = B;
	for(int i=0;i<n;i++)a[i] = X[i];
	int l=0, r=R+1;
//	cout << check(2) << '\n';
	while(l+1<r){
		int mid = (l+r)/2;
		if(check(mid)){
			l = mid;
		}else {
			r = mid;
		}
	}
	return l;
}

/*

3 20 0
1
2
4

1

*/

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