Submission #52175

#	Time	Username	Problem	Language	Result	Execution time	Memory
52175		Smelskiy	Watching (JOI13_watching)	C++14	100 / 100	398 ms	16788 KiB

watching

#include <bits/stdc++.h>
using namespace std;



int n;
int c1,c2;
int m;
int a[2005];
int dp[2005][2005];


inline bool f(long long mid) {
    for (int i=0;i<=n;++i)
        for (int j=0;j<=c1;++j)
            dp[i][j]=1e9;
    dp[0][0]=0;
    for (int i=1;i<=n;++i) {
        int last=i;
        while (last>0 && a[i]-a[last]+1<=mid) --last;
        for (int j=1;j<=c1;++j)
            dp[i][j]=min(dp[i-1][j-1],dp[last][j-1]);
        while (last>0 && a[i]-a[last]+1<=mid+mid) --last;
        for (int j=0;j<=c1;++j)
            dp[i][j]=min(dp[i][j],dp[last][j]+1);
    }
    for (int i=0;i<=c1;++i)
        if (dp[n][i]<=c2) {
//            cout<<i<<" "<<dp[n][i]<<'\n';
            return true;
        }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>c1>>c2;
    c1=min(c1,n);
    c2=min(c2,n);
    for (int i=1;i<=n;++i)
        cin>>a[i];
    sort(a+1,a+n+1);
    long long l=1;
    long long r=1e9;
    while (l<r-1ll) {
        long long mid=(l+r)/2ll;
        if (f(mid)) r=mid;
        else l=mid;
    }
    if (f(l)) r=l;
    cout<<r;
}

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