Submission #1281701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281701		dhuyyyy	Watching (JOI13_watching)	C++20	100 / 100	551 ms	31844 KiB

watching

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 2005;

int n, p, q, ans;

int a[N], dp[N][N];

bool ok(int mid){
    dp[0][0] = 0;
    for (int used = 0; used <= min(n,p); used++){
        int sid = 1;
        int lid = 1;
        for (int i = 1; i <= n; i++){
            dp[i][used] = 1e9;
            while (sid <= n && a[sid] <= a[i] - mid){
                sid++;
            }
            while (lid <= n && a[lid] <= a[i] - mid * 2){
                lid++;
            }
            if (used == 0) dp[i][used] = dp[lid - 1][used] + 1;
            else{
                dp[i][used] = min({dp[lid - 1][used] + 1,dp[sid - 1][used - 1]});
            }
        }
    }
    for (int i = 0; i <= min(n,p); i++){
        if (dp[n][i] <= q) return 1;
    }
    return 0;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+1+n);
    int l = 1, r = (int)1e9;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (ok(mid)){
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << ans;
    return 0;
}

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