Submission #289663

#	Time	Username	Problem	Language	Result	Execution time	Memory
289663		rocks03	Watching (JOI13_watching)	C++14	0 / 100	14 ms	5760 KiB

watching

#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, 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, int 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
• Subtask 2: 0 / 50