Submission #371550

#	Time	Username	Problem	Language	Result	Execution time	Memory
371550		ritul_kr_singh	Watching (JOI13_watching)	C++17	0 / 100	26 ms	492 KiB

watching

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int n, p, q, a[2001];

bool possible(int w){
    int dp[n+1][p+1];
    for(int i=0; i<=n; ++i){
        for(int j=0; j<=p; ++j){
            dp[i][j] = i ? 1e10 : 0;
        }
    }
    for(int i=1; i<=n; ++i){
        int f0 = upper_bound(a, a+n, max(0LL, a[i]-w)) - a - 1;
        int f1 = upper_bound(a, a+n, max(0LL, a[i]-2*w)) - a - 1;
        int g0 = 0, g1 = 0;
        while(g0+1<i and a[g0+1]+w-1<a[i]) ++g0;
        while(g1+1<i and a[g1+1]+2*w-1<a[i]) ++g1;
        assert(f0==g0 and f1==g1);
        for(int j=0; j<=p; ++j){
            // use
            if(j){
                dp[i][j] = min(dp[i][j], dp[f0][j-1]);
            }
            // don't
            dp[i][j] = min(dp[i][j], dp[f1][j] + 1);
        }
    }
    return dp[n][p]<=q;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> p >> q;
    a[0] = 0;
    for(int i=1; i<=n; ++i) cin >> a[i];
    sort(a+1, a+n+1);
    if(p>n or q>n){
        cout << 1 nl;
        return 0;
    }
    int low = 0, high = 1e9;
    while(low<high){
        int mid = (low+high)/2;
        if(possible(mid)) high = mid;
        else low = mid+1;
    }
    cout << low nl;
}

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