Submission #1304387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304387		quollcucumber`	Watching (JOI13_watching)	C++20	0 / 100	101 ms	15964 KiB

watching

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma target("avx2")
#define int long long
using namespace std;
int n, p, q;
int positions[2005];
int nextw[2005];
int next2w[2005];
bool seen[2005][2005];
int cached[2005][2005];
int dp(int big, int small) {
    if(seen[big][small]) return cached[big][small];
    int maxdist = -1;
    seen[big][small] = true;
    if(small != 0) {
        if(dp(big, small-1) == n-1) return cached[big][small] = n-1;
        maxdist = max(maxdist, nextw[dp(big, small-1) + 1]);
    }
    if(big != 0) {
        if(dp(big-1, small) == n-1) return cached[big][small] = n-1;
        maxdist = max(maxdist, next2w[dp(big - 1, small) + 1]);
    }
    return cached[big][small] = maxdist;
}

bool check(int val) {
    memset(seen, false, sizeof(seen));
    int r = 1;
    for(int i = 0; i < n; i++) {
        while(r != n && positions[r] < positions[i] + val) {
            r++;
        }
        nextw[i] = r - 1;
    }
    r = 1;
    for(int i = 0; i < n; i++) {
        while(r != n && positions[r] < positions[i] + 2 * val) {
            r++;
        }
        next2w[i] = r - 1;
    }
    if(dp(p, q) == n-1) {
        return true;
    }
    return false;
}
signed main() {
    cin >> n >> p >> q;
    for(int i = 0; i < n; i++) cin >> positions[i];
    sort(positions, positions + n);
    int l = 1, r = 1e9 + 5;
    while(r > l + 1) {
        int mid = (l  + r) / 2 - 1;
        if(check(mid)) {
            r = mid + 1;
        }else {
            l = mid + 1;
        }
    }
    cout<<l<<'\n';
}

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50