oj.uz

Submission #472934

# Submission time Handle Problem Language Result Execution time Memory
472934 2021-09-14T15:19:38 Z Joo Watching (JOI13_watching) C++17
0 / 100
 5 ms 8268 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 = 10, 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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8268 KB Output isn't correct
2 Halted 0 ms 0 KB -