oj.uz

Submission #80475

# Submission time Handle Problem Language Result Execution time Memory
80475 2018-10-20T23:31:23 Z mra2322001 Watching (JOI13_watching) C++14
100 / 100
 329 ms 16964 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, p, q, a[N];
int f[N][N], d1[N], d2[N];

bool solve(int w){
    memset(f, -1, sizeof(f));
    ///sort(a + 1, a + n + 1);
    f1(i, n){
        d1[i] = d2[i] = 0;
        d1[i] = lower_bound(a + 1, a + n + 1, a[i] - w + 1) - a;
        d2[i] = lower_bound(a + 1, a + n + 1, a[i] - 2*w + 1) - a;
    }
    /// f[i][j];
    f0(j, p + 1) f[0][j] = q;
    f1(i, n){
        f0(j, p + 1){
            if(j > 0){
                int k1 = d1[i];
                f[i][j] = f[max(k1 - 1, 0)][j - 1];
                f[i][j] = max(f[max(0, d2[i] - 1)][j] - 1, f[i][j]);
            }
            else{
                f[i][j] = f[max(d2[i] - 1, 0)][j] - 1;
            }
        }
    }
    f0(j, p + 1) if(f[n][j] >= 0) return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);


    cin >> n >> p >> q;
    f1(i, n) cin >> a[i];

    if(p + q >= n){
        cout << 1; return 0;
    }
    sort(a + 1, a + n + 1);

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

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16248 KB Output is correct
2 Correct 2 ms 16248 KB Output is correct
3 Correct 39 ms 16500 KB Output is correct
4 Correct 2 ms 16500 KB Output is correct
5 Correct 2 ms 16500 KB Output is correct
6 Correct 2 ms 16500 KB Output is correct
7 Correct 40 ms 16500 KB Output is correct
8 Correct 38 ms 16500 KB Output is correct
9 Correct 38 ms 16540 KB Output is correct
10 Correct 41 ms 16544 KB Output is correct
11 Correct 38 ms 16544 KB Output is correct
12 Correct 40 ms 16544 KB Output is correct
13 Correct 40 ms 16544 KB Output is correct
14 Correct 39 ms 16544 KB Output is correct
15 Correct 39 ms 16604 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16604 KB Output is correct
2 Correct 2 ms 16604 KB Output is correct
3 Correct 3 ms 16604 KB Output is correct
4 Correct 3 ms 16604 KB Output is correct
5 Correct 2 ms 16604 KB Output is correct
6 Correct 2 ms 16604 KB Output is correct
7 Correct 45 ms 16824 KB Output is correct
8 Correct 65 ms 16844 KB Output is correct
9 Correct 177 ms 16856 KB Output is correct
10 Correct 329 ms 16856 KB Output is correct
11 Correct 65 ms 16856 KB Output is correct
12 Correct 217 ms 16916 KB Output is correct
13 Correct 49 ms 16916 KB Output is correct
14 Correct 55 ms 16964 KB Output is correct
15 Correct 54 ms 16964 KB Output is correct