Submission #1147563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147563		VMaksimoski008	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	60 / 100	2093 ms	16092 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=0, 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=L; i<=n; i++) {
            int x=max(i-R+1, opt[i]), y=i-L+1;
            for(int j=x-1; j<=y-1; j++)
                if(dp[j]) dp[i] = 1;
        }

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

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

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