Submission #944120

#	Time	Username	Problem	Language	Result	Execution time	Memory
944120		goduadzesaba	Watching (JOI13_watching)	C++17	100 / 100	211 ms	16208 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,p,q,l,r,md,ans,a[N],dp[N][N];
bool check(int w){
    for (int i=1; i<=n; i++){
        int l1=0, l2=0;
        for (int j=0; j<=n; j++) dp[i][j]=1e9;
        for (int j=i; j>=0; j--){
            while(a[l1+1]<=a[i]-w) l1++;
            while(a[l2+1]<=a[i]-2*w) l2++;
            if(j > 0) dp[i][j]=dp[l1][j-1];
            dp[i][j]=min(dp[i][j],dp[l2][j]+1);
        }
    }
    for (int i=0; i<=p; i++) {
        if(dp[n][i]<=q) return 1;
    }
    return 0;
}
int main() {
    cin>>n>>p>>q;
    p=min(p, n);
    q=min(q, n);
    for (int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    l=1; r=1e9;
    while (l<=r){
        md=(l+r)/2;
        if (check(md)){
            ans=md; r=md-1;
        }
        else l=md+1;
    }
    cout<<ans;
}

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