oj.uz

Submission #83704

# Submission time Handle Problem Language Result Execution time Memory
83704 2018-11-10T03:06:09 Z mra2322001 Watching (JOI13_watching) C++14
100 / 100
 383 ms 16568 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], d1[N], d2[N], f[N][N];

bool check(int dist){
    /// f(i, j) den i, dung j camera nho
    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;
    f1(i, n){
        f0(j, p + 1){
            if(j==0){
                int x = max(d2[i], 0);
                f[i][j] = f[x - 1][j] - 1;
                continue;
            }
            int x = max(d1[i] - 1, 0);
            f[i][j] = f[x][j - 1];
            x = max(d2[i] - 1, 0);
            f[i][j] = max(f[i][j], f[x][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];

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8732 KB Output is correct
2 Correct 2 ms 8732 KB Output is correct
3 Correct 2 ms 8732 KB Output is correct
4 Correct 2 ms 8732 KB Output is correct
5 Correct 2 ms 8732 KB Output is correct
6 Correct 3 ms 8732 KB Output is correct
7 Correct 15 ms 8876 KB Output is correct
8 Correct 39 ms 9788 KB Output is correct
9 Correct 151 ms 14776 KB Output is correct
10 Correct 383 ms 16568 KB Output is correct
11 Correct 32 ms 16568 KB Output is correct
12 Correct 193 ms 16568 KB Output is correct
13 Correct 17 ms 16568 KB Output is correct
14 Correct 19 ms 16568 KB Output is correct
15 Correct 18 ms 16568 KB Output is correct