Submission #1147554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147554		VMaksimoski008	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	0 / 100	17 ms	1616 KiB

plaukimo_varzybos

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, L, R; cin >> n >> L >> R;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a.begin()+1, a.end());

    int l=1, r=1e6, ans=1e6;
    while(l <= r) {
        int mid = (l + r) / 2, j = 1;
        vector<int> opt(n+1), dp(n+1), good;
        for(int i=1; i<=n; i++) {
            while(j < i && a[i] - a[j] > mid) j++;
            opt[i] = j;
        }

        dp[0] = 1;
        good.push_back(0);
        
        j = 0;
        for(int i=L; i<=n; i++) {
            while(j+1 < good.size() && good[j+1] <= i-L) j++;
            if(opt[i] <= i-L+1 && good[j] >= max(i-R+1, opt[i])-1) dp[i] = 1;
            if(dp[i]) good.push_back(i);
        }

        if(dp[n]) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
}

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