Submission #1239469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239469		trinm01	Watching (JOI13_watching)	C++20	50 / 100	1097 ms	32036 KiB

watching

//  #pragma GCC optimize("O3")
//  #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzd,popd")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e6+3;
const int MAXN = 2e3 + 5;
const ll oo = 1e18 + 7;
const ll base = 350;  

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

int f[MAXN][MAXN];
int dp(int i, int t, int k){
    if(i>n){
        return 0;
    }
    if(f[i][t]!=-1){
        return f[i][t];
    }
    int id=upper_bound(a+1, a+1+n+1, a[i]+k-1)-a-1;
    int ans=oo;
    if(t+1<=p && id+1!=i){
        ans=dp(id+1, t+1, k);
    }
    id=upper_bound(a+1, a+1+n+1, a[i]+2*k-1)-a-1;
    if(id+1==i){
        return f[i][t]=oo;
    }
    ans=min(ans, dp(id+1, t, k)+1);
    return f[i][t]=ans;
}

int check(int k){
    memset(f, -1, sizeof f);
    if(dp(1, 0, k)<=q){
        return 1;
    }
    return 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);   

    // freopen("test.txt", "r", stdin);
    //  freopen("o2.out", "w", stdout);
    

    cin >> n >> p >> q;
    FOR(i, 1, n){
        cin >> a[i];
    }
    sort(a+1, a+1+n);
    a[n+1]=oo;

    int l=0, r=1e9, ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }

    cout << ans;

    return 0;
}

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