oj.uz

Submission #371542

# Submission time Handle Problem Language Result Execution time Memory
371542 2021-02-26T21:12:20 Z ritul_kr_singh Watching (JOI13_watching) C++17
0 / 100
 1000 ms 23936 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int n, p, q, a[2001];

bool possible(int w){
    int dp[n+1][p+1];
    for(int i=0; i<=n; ++i){
        for(int j=0; j<=p; ++j){
            dp[i][j] = i ? 1e10 : 0;
        }
    }
    for(int i=1; i<=n; ++i){
        for(int j=0; j<=p; ++j){
            // use
            if(j){
                int f = upper_bound(a, a+n, max(0LL, a[i]-w)) - a - 1;
                dp[i][j] = min(dp[i][j], dp[f][j-1]);
            }
            // don't
            int f = upper_bound(a, a+n, max(0LL, a[i]-2*w)) - a - 1;
            dp[i][j] = min(dp[i][j], dp[f][j] + 1);
        }
    }
    return dp[n][p]<=q;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> p >> q;
    a[0] = 0;
    for(int i=1; i<=n; ++i) cin >> a[i];
    sort(a+1, a+n+1);
    p = min(p, n);
    int low = 0, high = 1e9;
    while(low<high){
        int mid = (low+high)/2;
        if(possible(mid)) high = mid;
        else low = mid+1;
    }
    cout << low nl;
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 1081 ms 23936 KB Time limit exceeded
4 Halted 0 ms 0 KB -