Submission #1311687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311687		Zone_zonee	Watching (JOI13_watching)	C++20	100 / 100	123 ms	16180 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10;

int n, p, q, a[N];
int dp[N][N];
bool valid(int w){
    for(int i = 1; i <= n; ++i){
        int large = upper_bound(a+1, a+n+1, a[i]-2*w) - (a+1);
        int small = upper_bound(a+1, a+n+1, a[i]-w) - (a+1);
        for(int j = 0; j <= q; ++j){
            dp[i][j] = 1e9;
            dp[i][j] = min( (large == 0 || j == 0) ? (j == 0 ? N : 0) : dp[large][j-1],
                            (small == 0) ? 1 : dp[small][j]+1);
        }
    }
    return dp[n][q] <= p;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> p >> q;
    if(p+q >= n){
        cout << 1 << '\n';
        return 0;
    }
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a+1, a+n+1);
    int l = 1, r = 1e9;
    while(l < r){
        int mid = (l+r)>>1;
        if(valid(mid)) r = mid;
        else l = mid+1;
    }
    cout << r << '\n';
}

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