oj.uz

Submission #472935

# Submission time Handle Problem Language Result Execution time Memory
472935 2021-09-14T15:20:16 Z Joo Watching (JOI13_watching) C++17
50 / 100
 1000 ms 14148 KB 
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int N = 2e3+10;
int n,P,Q,dp[N][N];

main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> P >> Q;
    vector<int> a(n+1, 0);
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    if(P+Q >= n){
        cout << "1\n";
        return 0;
    }

    int l = 1, r = 1e9, ans = -1;
    while(l <= r){
        int mid = (l+r)/2;
        for(int i=1; i<=n; i++){
            for(int q=0,j; q<=Q; q++){
                dp[i][q] = 1e9;
                if(q > 0){
                    j = lower_bound(a.begin()+1, a.end(), a[i]-2*mid+1)-a.begin();
                    dp[i][q] = dp[j-1][q-1];
                }
                j = lower_bound(a.begin()+1, a.end(), a[i]-mid+1)-a.begin();
                dp[i][q] = min(dp[i][q], dp[j-1][q]+1);
            }
        }

        if(dp[n][Q] <= P){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << ans << "\n";
}

Compilation message

watching.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main(){
      | ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 708 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8396 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 29 ms 8396 KB Output is correct
8 Execution timed out 1091 ms 14148 KB Time limit exceeded
9 Halted 0 ms 0 KB -