oj.uz

Submission #83705

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

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) f1(j, p) f[i][j] = -1e9;
    /// f[i][j] den i, dung j camera thi con lai max la bao nhieu
    f1(i, n){
        f0(j, p + 1){
            f[i][j] = f[d2[i] - 1][j] - 1;
            if(j > 0){
                f[i][j] = max(f[i][j], f[d1[i] - 1][j - 1]);
            }
        }
    }
    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 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 1020 KB Output is correct
8 Correct 3 ms 1020 KB Output is correct
9 Correct 4 ms 1020 KB Output is correct
10 Correct 3 ms 1020 KB Output is correct
11 Correct 3 ms 1020 KB Output is correct
12 Correct 3 ms 1020 KB Output is correct
13 Correct 2 ms 1020 KB Output is correct
14 Correct 3 ms 1080 KB Output is correct
15 Correct 2 ms 1080 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8688 KB Output is correct
2 Correct 2 ms 8688 KB Output is correct
3 Correct 6 ms 8688 KB Output is correct
4 Correct 2 ms 8688 KB Output is correct
5 Correct 2 ms 8688 KB Output is correct
6 Correct 2 ms 8688 KB Output is correct
7 Correct 15 ms 8700 KB Output is correct
8 Correct 38 ms 9608 KB Output is correct
9 Correct 148 ms 14588 KB Output is correct
10 Correct 364 ms 16252 KB Output is correct
11 Correct 32 ms 16252 KB Output is correct
12 Correct 186 ms 16252 KB Output is correct
13 Correct 18 ms 16252 KB Output is correct
14 Correct 20 ms 16252 KB Output is correct
15 Correct 21 ms 16252 KB Output is correct