oj.uz

Submission #52150

# Submission time Handle Problem Language Result Execution time Memory
52150 2018-06-24T09:48:09 Z Smelskiy Watching (JOI13_watching) C++14
0 / 100
 1000 ms 376 KB 
#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);
    cin>>m;
    for (int i=1;i<=m;++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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -