oj.uz

답안 #80475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80475 2018-10-20T23:31:23 Z mra2322001 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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