| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301169 | pashtetkas | 쌀 창고 (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
bool check(int k, vector<long long>&pref, int R, long long B){
long long min_wyn = LLONG_MAX;
int n = R - k + 1;
for(int l = 1; l<=n; l++){
int r = l + k - 1;
int m = l + (k/2);
long long temp_wyn = (m - l)*pref[m] - (pref[m] - pref[l-1]);
temp_wyn += (pref[r] - pref[m]) - (r - (m+1) + 1)*pref[m];
min_wyn = min(min_wyn, temp_wyn);
}
if(min_wyn <= B)return true;
else return false;
}
long long besthub(int R, int L, vector<int>&X, long long B){
if(B == 0)return 0;
vector<long long>pref(R+7, 0);
for(int i = 1; i<=R; i++)pref[i] = pref[i-1] + X[i-1];
int l = 1;
int r = R;
int wyn = 0;
while(l<=r){
int mid = (l+r)/2;
if(check(mid, pref, R, B)){
l = mid + 1;
wyn = max(wyn, mid);
}
else r = mid - 1;
}
return wyn;
}