Submission #289671

#	Time	Username	Problem	Language	Result	Execution time	Memory
289671		rocks03	Watching (JOI13_watching)	C++14	100 / 100	734 ms	35064 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;
ll a[MAXN], nxt[2][MAXN], memo[MAXN][MAXN];

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

int f(int q, int ind, ll w){
    if(ind == N){
        return 0;
    }
    if(memo[q][ind] != -1){
        return memo[q][ind];
    }
    int ans = P+1;
    int j = nxt[0][ind];
    ans = min(ans, f(q, j, w) + 1);
    if(q){
        int j = nxt[1][ind];
        ans = min(ans, f(q-1, j, w));
    }
    memo[q][ind] = ans;
    return memo[q][ind];
}

bool good(ll w){
    if(P + Q >= N) return true;
    for(int i = 0; i < N; i++){
        nxt[0][i] = upper_bound(a+i, a+N, a[i] + w - 1) - a;
        nxt[1][i] = upper_bound(a+i, a+N, a[i] + 2*w - 1) - a;
    }
    memset(memo, -1, sizeof(memo));
    return (f(Q, 0, w) <= P);
}

void solve(){
    read();
    sort(a, a+N);
    ll l = 0, 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: 50 / 50
• Subtask 2: 50 / 50