| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1270983 | cmiuc | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include "ricehub.h"
using namespace std;
long long suf[1<<17], pre[1<<17];
int besthub(int n, int L, int x[], int B){
for (int i=n-1;i>=0;i--)
suf[i] = suf[i + 1] + x[i];
int Ans = 0;
for (int i=0;i<n;i++){
pre[i] = (i == 0 ? 0 : pre[i-1]) + x[i];
long long l = -1, r = L + 1, lft, rgt, cst;
while (l + 1 < r){
int mid = (l + r) / 2;
int k2 = upper_bound(x + i, x + n, x[i] + mid) - x;
int k1 = upper_bound(x, x + n, x[i] - mid - 1) - x;
long long nB = (suf[i] - suf[k2]) - (k2 - i) * x[i];
nB = 1LL * (i - k1 + 1) * x[i] - (pre[i] - (k1 == 0 ? 0 : pre[k1-1])) + nB;
// if (i == 2)
// cout<<x[i]<<" "<<l<<" "<<r<<" "<<k1<<" "<<k2<<" "<<nB<<endl;
if (nB <= B)
l = mid, lft = k1, rgt = k2, cst = nB;
else
r = mid;
}
long long mn = B + 1;
if (lft > 0)
mn = x[i] - x[lft - 1];
if (rgt < n)
mn = min(mn, 0LL + x[rgt] - x[i]);
// cout<<i<<" "<<l<<" "<<lft<<" "<<rgt<<" "<<cst<<" "<<mn<<endl;
Ans = max(Ans + 0LL, rgt - lft + (B - cst) / mn);
}
return Ans;
}