| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301140 | b_malinowski | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using i64 = int64_t;
bool Spr(vector<i64>& fields, i64 B, i64 amo)
{
int cost = 0;
for (int i = 0; i < amo; i++)
{
cost += abs(fields[i] - fields[amo / 2]);
}
if (cost <= B)
{
return true;
}
for (int i = 1; i + amo <= 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;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
i64 N, M, B;
cin >> N >> M >> B;
vector<i64> fields(N);
for (i64 i = 0; i < N; i++)
{
cin >> fields[i];
}
i64 pocz = 0, kon = N, srodek;
while (pocz < kon)
{
srodek = (pocz + kon + 1) / 2;
if (Spr(fields, B, srodek))
{
pocz = srodek;
}
else
{
kon = srodek - 1;
}
}
cout << pocz << "\n";
return 0;
}