oj.uz

Submission #289664

# Submission time Handle Problem Language Result Execution time Memory
289664 2020-09-02T22:01:48 Z rocks03 Watching (JOI13_watching) C++14
0 / 100
 15 ms 5504 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pld pair<long double, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define SZ(x) ((int)(x).size())
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2e3+100;
int N, P, Q;
ll a[MAXN];
int memo[100+10][100+10][100+10];

void read(){
    cin >> N >> P >> Q;
    for(int i = 0; i < N; i++) cin >> a[i];
}

int f(int p, int q, int ind, ll w){
    if(ind == N) return true;
    if(memo[p][q][ind] != -1){
        return memo[p][q][ind];
    }
    int ans = 0;
    if(p){
        int nxt = upper_bound(a, a+N, a[ind] + w - 1) - a;
        ans = max(ans, f(p-1, q, nxt, w));
    }
    if(q){
        int nxt = upper_bound(a, a+N, a[ind] + 2*w - 1) - a;
        ans = max(ans, f(p, q-1, nxt, w));
    }
    memo[p][q][ind] = ans;
    return ans;
}

bool good(ll k){
    if(P + Q >= N) return true;
    memset(memo, -1, sizeof(memo));
    return (f(P, Q, 0, k) > 0);
}

void solve(){
    read();
    sort(a, a+N);
    ll l = -1, r = 1e10;
    while(r - l > 1){
        ll m = (l + r) / 2;
        if(good(m)) r = m;
        else l = m;
    }
    cout << r;
}

int main(){
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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