oj.uz

Submission #90055

# Submission time Handle Problem Language Result Execution time Memory
90055 2018-12-20T04:39:51 Z mra2322001 Watching (JOI13_watching) C++14
100 / 100
 325 ms 16972 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 2002;

int n, small, big, a[N], f[N][N], d1[N], d2[N];

bool check(int x){
    f1(i, n){
        d1[i] = lower_bound(a + 1, a + n + 1, a[i] - x + 1) - a;
        d2[i] = lower_bound(a + 1, a + n + 1, a[i] - 2*x + 1) - a;
    }
    memset(f, 0x3f3f3f, sizeof(f));
    f0(j, small + 1) f[0][j] = 0;
    f1(i, n){
        f0(j, small + 1){
            /// dung 1 small
            if(j > 0) f[i][j] = f[d1[i] - 1][j - 1];
            f[i][j] = min(f[i][j], f[d2[i] - 1][j] + 1);
        }
    }
    return f[n][small] <= big;
}

int main(){
    ios_base::sync_with_stdio(0);
 
    cin >> n >> small >> big;
    f1(i, n) cin >> a[i];
    if(small + big >= n){
        cout << 1; return 0;
    }
    sort(a + 1, a + n + 1);

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

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16120 KB Output is correct
2 Correct 2 ms 16120 KB Output is correct
3 Correct 41 ms 16476 KB Output is correct
4 Correct 2 ms 16476 KB Output is correct
5 Correct 2 ms 16476 KB Output is correct
6 Correct 2 ms 16476 KB Output is correct
7 Correct 41 ms 16528 KB Output is correct
8 Correct 38 ms 16528 KB Output is correct
9 Correct 40 ms 16544 KB Output is correct
10 Correct 41 ms 16544 KB Output is correct
11 Correct 42 ms 16720 KB Output is correct
12 Correct 44 ms 16720 KB Output is correct
13 Correct 41 ms 16720 KB Output is correct
14 Correct 44 ms 16720 KB Output is correct
15 Correct 40 ms 16720 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16720 KB Output is correct
2 Correct 2 ms 16720 KB Output is correct
3 Correct 2 ms 16720 KB Output is correct
4 Correct 2 ms 16720 KB Output is correct
5 Correct 2 ms 16720 KB Output is correct
6 Correct 2 ms 16720 KB Output is correct
7 Correct 50 ms 16936 KB Output is correct
8 Correct 68 ms 16972 KB Output is correct
9 Correct 157 ms 16972 KB Output is correct
10 Correct 325 ms 16972 KB Output is correct
11 Correct 67 ms 16972 KB Output is correct
12 Correct 194 ms 16972 KB Output is correct
13 Correct 50 ms 16972 KB Output is correct
14 Correct 51 ms 16972 KB Output is correct
15 Correct 51 ms 16972 KB Output is correct