제출 #1249331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249331		Nurislam	Rice Hub (IOI11_ricehub)	C++20	17 / 100	1 ms	328 KiB

ricehub

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "ricehub.h"

using namespace std;
typedef long long ll;

ll inf = 1e18;

int besthub(int n, int L, int A[], ll b){
	vector<int> a(n);
	for(int i = 0; i < n; i ++ ) a[i] = A[i];
	sort(a.begin(), a.end());
	ll ans = 0;
	
	ll cur = 0;
	ll l = 0, r = 0;
	
	for(int i = 0; i < n; i ++ ) {
		while(r+1 < n && a[i] - a[l] > a[r+1] - a[l]){
			r ++;
			cur += a[r] - a[i];
			cur += a[i] - a[l];
			l ++;
		};
		
		
		while(1) {
			//cout << 1 << endl;
			ll lf = (l== 0 ? inf: a[i] - a[l-1]);
			ll ri = (r==n-1 ? inf: a[r+1] - a[i]);
			
			if(lf == inf && ri == inf) break;
			
			if(lf <= ri && lf + cur <= b) {
				cur += lf;
				l -- ;
			}else if(ri < lf && ri + cur <= b) {
				cur += ri;
				r ++ ;
			}else break;
			
		};
		//cout << l << ' ' << r << ' ' << i << '\n';
		
		ans = max(ans, r-l+1);
		
		if(i+1 < n) {
			cur += ((i-l+1) - (r - i)) * (a[i+1]-a[i]); 
			if(r < i+1) r++;
			while(l <= i && cur > b) {
				cur -= (a[i+1] - a[l]);
				l ++ ;
			};
		};
	};
	
	return ans;
}

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