Submission #577830

#	Time	Username	Problem	Language	Result	Execution time	Memory
577830		teki	Watching (JOI13_watching)	C++11	100 / 100	410 ms	23104 KiB

watching

#include <bits/stdc++.h>

typedef long long ll;

#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
const ll MN = 1000000007;

using namespace std;

ll n,p,q;
ll niz[2001],nizP[2001],nizQ[2001];
ll dp[2001][2001];

bool check(ll pos) {
    for (ll i = 1; i<=n; i++) {
        nizP[i] = (lower_bound(niz+1,niz+n+1,niz[i]+1*pos))-niz-1;
        nizQ[i] = (lower_bound(niz+1,niz+n+1,niz[i]+2*pos))-niz-1;

        for (ll j = 0; j<=i; j++) dp[i][j] = MN*MN;
    }

    for (ll i = 1; i<=n; i++) {
        for (ll j = 0; j<i; j++) {
            dp[nizP[i]][j] = min(dp[nizP[i]][j], dp[i-1][j]+1);
            dp[nizQ[i]][j+1] = min(dp[nizQ[i]][j+1], dp[i-1][j]);
        }
    }

    for (ll i = 0; i<=q; i++) {
        if (dp[n][i] <= p) return true;
    }

    return false;
}

int main()
{
    #if LOCAL_DEBUG
        fstream cin("in.txt");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>p>>q;

    if (p+q >= n) {
        cout<<1<<endl;
        return 0;
    }

    for (ll i = 1; i<=n; i++) cin>>niz[i];
    sort(niz+1,niz+n+1);

    ll left = 1, right = MN*MN;

    while (left < right) {
        ll mid = (left + right)/2;

        if (check(mid)) right = mid;
        else left = mid+1;
    }

    cout<<left<<endl;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50