| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301141 | b_malinowski | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
bool Spr(vector<i64>& fields, i64 B, i64 amo)
{
if (amo == 0) return true;
i64 cost = 0;
for (i64 i = 0; i < amo; i++)
cost += llabs(fields[i] - fields[amo / 2]);
if (cost <= B) return true;
for (i64 i = 1; i + amo <= (i64)fields.size(); i++)
{
cost += fields[i + amo - 1] - 2 * fields[i + amo / 2] + fields[i - 1];
cost += (fields[amo / 2 + 1] - fields[amo / 2]) * (amo / 2 * 2 - amo);
if (cost <= B) return true;
}
return false;
}
long long besthub(int R, int L, long long B, long long X[])
{
vector<i64> fields(R);
for (int i = 0; i < R; i++) fields[i] = X[i];
i64 pocz = 0, kon = R;
while (pocz < kon)
{
i64 srodek = (pocz + kon + 1) / 2;
if (Spr(fields, B, srodek))
pocz = srodek;
else
kon = srodek - 1;
}
return pocz;
}