| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 895851 | 2023-12-30T22:33:20 Z | vjudge1 | 쌀 창고 (IOI11_ricehub) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
int n, budget;
vector<int> psum;
vector<int> ssum;
bool check(int rice) {
int middle = (rice-1) / 2;
int right = middle+(rice)/2;
int minb = 1e9;
for (int i = 0; i <= n - rice; i++) {
int b = psum[i+right] - psum[i+middle] + ssum[i] - ssum[i+middle];
minb = min(b, minb);
}
//cout << "minb: " << minb << endl;
if (minb <= budget) return true;
return false;
}
int besthub(int r, ll maxcoor, int a[], int b) {
n = r;
budget = b;
int diff[n-1];
for (int i = 0; i < n-1; i++) {
diff[i] = a[i+1] - a[i];
}
psum.resize(n, 0);
ssum.resize(n, 0);
for (int i = 1; i < n; i++) {
psum[i] = a[i-1] + psum[i-1];
}
for (int i = n-2; i >= 0; i--) {
ssum[i] = a[i] + ssum[i+1];
}
int l = 1;
while (l < r) {
int mid = (l + r + 1) / 2;
//cout << "mid: " << mid << endl;
if (check(mid)) {
l = mid;
}
else {
r = mid - 1;
}
}
return l;
}
// signed main() {
// int r, l, b; cin >> r >> l >> b;
// int x[r];
// for (int i = 0; i < r; i++) cin >> x[i];
// besthub(r, l, x, b);
// }