oj.uz

Submission #83706

# Submission time Handle Problem Language Result Execution time Memory
83706 2018-11-10T03:18:15 Z mra2322001 Watching (JOI13_watching) C++14
100 / 100
 315 ms 16356 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, a[N], f[N][N], d1[N], d2[N], p, q;

bool check(int dist){
    f1(i, n){
        d1[i] = lower_bound(a + 1, a + n + 1, a[i] - dist + 1) - a;
        d2[i] = lower_bound(a + 1, a + n + 1, a[i] - 2*dist + 1) - a;
    }
    f0(i, p + 1) f[0][i] = q;
    f1(i, n){
        f0(j, p + 1){
            f[i][j] = -1e9;
            f[i][j] = f[d2[i] - 1][j] - 1;
            if(j - 1 >= 0){
                f[i][j] = max(f[d1[i] - 1][j - 1], f[i][j]);
            }
        }
    }
    return f[n][p] >= 0;
}

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

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

    sort(a + 1, a + n + 1);
    if(p + q >= n){
        cout << 1;
        return 0;
    }
    int l = 1, r = 1e9 + 5, 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 3 ms 756 KB Output is correct
2 Correct 3 ms 756 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 3 ms 756 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 3 ms 916 KB Output is correct
8 Correct 3 ms 1092 KB Output is correct
9 Correct 3 ms 1092 KB Output is correct
10 Correct 2 ms 1092 KB Output is correct
11 Correct 3 ms 1092 KB Output is correct
12 Correct 3 ms 1092 KB Output is correct
13 Correct 3 ms 1092 KB Output is correct
14 Correct 3 ms 1092 KB Output is correct
15 Correct 3 ms 1092 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8684 KB Output is correct
2 Correct 2 ms 8684 KB Output is correct
3 Correct 2 ms 8684 KB Output is correct
4 Correct 3 ms 8684 KB Output is correct
5 Correct 2 ms 8684 KB Output is correct
6 Correct 3 ms 8684 KB Output is correct
7 Correct 19 ms 8700 KB Output is correct
8 Correct 51 ms 9596 KB Output is correct
9 Correct 171 ms 14640 KB Output is correct
10 Correct 315 ms 16356 KB Output is correct
11 Correct 29 ms 16356 KB Output is correct
12 Correct 203 ms 16356 KB Output is correct
13 Correct 22 ms 16356 KB Output is correct
14 Correct 18 ms 16356 KB Output is correct
15 Correct 18 ms 16356 KB Output is correct