# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1139866 | adelina | Swimming competition (LMIO18_plaukimo_varzybos) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int Nmax = 1e6 + 5;
int v[Nmax];
int n, a, b;
bool ok(int dif)
{
int dr = 1, ok = 0;
deque<int>st;
//cout << dif << ": " << '\n';
st.push_front(1);
while(dr <= n && !st.empty())
{
if(dr - st.front() + 1 >= a)
{
if(dr - st.front() + 1 < b && v[dr + 1] - v[st.front()] <= dif)
dr ++, st.push_back(dr);
else
st.pop_front();
}
else
dr ++;
}
dr --;
if(st.empty() st.back() != n + 1)
return false;
return true;
}
int main()
{
int i, st, dr, mid, ans = 0;
cin >> n >> a >> b;
for(i = 1; i <= n; i ++)
cin >> v[i];
sort(v + 1, v + n + 1);
st = 0; dr = v[n] - v[1];
while(st <= dr)
{
mid = (st + dr) / 2;//dif maxima
if(ok(mid))
{
ans = mid;
dr = mid - 1;
}
else
st = mid + 1;
}
cout << ans;
return 0;
}