제출 #1147495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147495		gramathegod	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	100 / 100	428 ms	6376 KiB

plaukimo_varzybos

#include <bits/stdc++.h>

#define N 1000000

using namespace std;

int n,a,b;

vector<int> v;

bool check(int ans){
    deque<int> dq;
    int index=a-1;
    dq.push_back(-1);
    while (index<n && !dq.empty()){
        if (index-dq.front()>=a){
            if (index-dq.front()<=b && v[index]-v[dq.front()+1]<=ans){
                dq.push_back(index);
                index++;
            }
            else{
                dq.pop_front();
            }
        }
        else{
            index++;
        }
    }

    return ((!dq.empty()) && (dq.back()==n-1));
}

int bin(){
    int left=0, right=v[n-1]-v[0]+1,mid;
    int ans=right;
    while (left<=right){
        mid=(left+right)/2;

        if (check(mid)){
            ans=mid;
            right=mid-1;
        }
        else{
            left=mid+1;
        }
    }
    return ans;
}

int main()
{
    cin>>n>>a>>b;
    v.resize(n);
    for (int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    cout<<bin();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40