Submission #1147548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147548		VMaksimoski008	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	0 / 100	16 ms	1992 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), pref(n+1);
        for(int i=1; i<=n; i++) {
            while(j < i && a[i] - a[j] > mid) j++;
            opt[i] = j;
        }

        dp[0] = pref[0] = 1;
        for(int i=1; i<=L; i++) pref[i] = 1;
        for(int i=L; i<=n; i++) {
            int x=max(i-R+1, opt[i]), y=i-L+1;
            
            if(x <= y) {
                int cnt = pref[y-1];
                if(x > 1) cnt -= pref[x-2];
                if(cnt) dp[i] = 1;
            }

            pref[i] = pref[i-1] + dp[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