oj.uz

Submission #52175

# Submission time Handle Problem Language Result Execution time Memory
52175 2018-06-24T13:38:27 Z Smelskiy Watching (JOI13_watching) C++14
100 / 100
 398 ms 16788 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);
    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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 764 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 4 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 4 ms 1224 KB Output is correct
7 Correct 3 ms 1224 KB Output is correct
8 Correct 3 ms 1224 KB Output is correct
9 Correct 3 ms 1224 KB Output is correct
10 Correct 3 ms 1224 KB Output is correct
11 Correct 4 ms 1224 KB Output is correct
12 Correct 3 ms 1224 KB Output is correct
13 Correct 3 ms 1224 KB Output is correct
14 Correct 3 ms 1252 KB Output is correct
15 Correct 3 ms 1256 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 8856 KB Output is correct
2 Correct 2 ms 8856 KB Output is correct
3 Correct 306 ms 16576 KB Output is correct
4 Correct 398 ms 16724 KB Output is correct
5 Correct 33 ms 16724 KB Output is correct
6 Correct 385 ms 16780 KB Output is correct
7 Correct 34 ms 16780 KB Output is correct
8 Correct 52 ms 16780 KB Output is correct
9 Correct 180 ms 16780 KB Output is correct
10 Correct 397 ms 16780 KB Output is correct
11 Correct 37 ms 16780 KB Output is correct
12 Correct 224 ms 16788 KB Output is correct
13 Correct 35 ms 16788 KB Output is correct
14 Correct 34 ms 16788 KB Output is correct
15 Correct 29 ms 16788 KB Output is correct