oj.uz

Submission #95280

# Submission time Handle Problem Language Result Execution time Memory
95280 2019-01-29T14:10:33 Z dalgerok Watching (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -