| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1354881 | Charizard2021 | 쌀 창고 (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
int besthub(int n, int L, int X[], long long B){
vector<long long> x(n);
vector<long long> pref(n);
map<long long, long long> mp;
for(long long i = 0; i < n; i++){
x[i] = X[i];
mp[x[i]]++;
pref[i] = x[i];
if(i != 0){
pref[i] += pref[i - 1];
}
}
long long ans = 0;
for(int i = 0; i < n; i++){
long long low = 0;
long long high = 1e9;
long long res = 0;
while(low <= high){
long long mid = (low + high)/2;
int L = lower_bound(x.begin(), x.end(), x[i] - mid) - x.begin();
int R = upper_bound(x.begin(), x.end(), x[i] + mid) - x.begin();
R--;
long long val3 = (i == 0 ? 0 : pref[i - 1]) - (L == 0 ? 0 : pref[L - 1]);
long long val1 = x[i] * (i - L) - val3;
long long val4 = pref[R] - pref[i];
long long val2 = val4 - (R - i) * x[i];
if(val1 + val2 <= B){
res = mid;
low = mid + 1;
}
else{
high = mid - 1;
}
}
long long L = lower_bound(x.begin(), x.end(), x[i] - mid) - x.begin();
long long R = upper_bound(x.begin(), x.end(), x[i] + mid) - x.begin();
R--;
long long val3 = (i == 0 ? 0 : pref[i - 1]) - (L == 0 ? 0 : pref[L - 1]);
long long val1 = x[i] * (i - L) - val3;
long long val4 = pref[R] - pref[i];
long long val2 = val4 - (R - i) * x[i];
long long val = (B - val1 - val2)/(mid + 1);
val = min(val, mp[x[i] - mid - 1] + mp[x[i] + mid + 1]);
ans = max(ans, R - L + 1 + val);
}
return (int)ans;
}