oj.uz

답안 #95280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95280 2019-01-29T14:10:33 Z dalgerok 구경하기 (JOI13_watching) C++14
50 / 100
 641 ms 31996 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 2005;




int n, p, q, a[N], d1[N], d2[N], dp[N][N];

inline bool check(int w){
    for(int i = 1; i <= n; i++){
        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;
    }
    memset(dp, 63, sizeof(dp));
    for(int i = 0; i <= p; i++){
        dp[0][i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= p; j++){
            if(j > 0){
                dp[i][j] = dp[d1[i] - 1][j - 1];
            }
            dp[i][j] = min(dp[i][j], dp[d2[i] - 1][j] + 1);
        }
    }
    return dp[n][p] <= q;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> p >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int l = 1, r = 1e9;
    while(r - l > 1){
        int mid = (r + l) >> 1;
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }
    if(check(l)){
        cout << l;
    }
    else{
        cout << r;
    }
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 16120 KB Output is correct
2 Correct 37 ms 15992 KB Output is correct
3 Correct 48 ms 15992 KB Output is correct
4 Correct 641 ms 16248 KB Output is correct
5 Correct 37 ms 16120 KB Output is correct
6 Correct 638 ms 15992 KB Output is correct
7 Correct 42 ms 16120 KB Output is correct
8 Correct 43 ms 16116 KB Output is correct
9 Correct 44 ms 15992 KB Output is correct
10 Correct 41 ms 16120 KB Output is correct
11 Correct 41 ms 16096 KB Output is correct
12 Correct 46 ms 16120 KB Output is correct
13 Correct 44 ms 16056 KB Output is correct
14 Correct 56 ms 16120 KB Output is correct
15 Correct 44 ms 16120 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 16092 KB Output is correct
2 Correct 51 ms 16120 KB Output is correct
3 Correct 274 ms 16144 KB Output is correct
4 Runtime error 369 ms 31996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -