Submission #867250

#	Time	Username	Problem	Language	Result	Execution time	Memory
867250		HaiHoang	Watching (JOI13_watching)	C++17	100 / 100	212 ms	31936 KiB

watching

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e9;
ll n, P, Q;
vector<ll> a;
ll L[2005][2];
ll dp[2005][2005];
bool check(ll w)
{
    for(ll i=0; i<=n+2; i++)
    {
        for(ll j=0; j<=n+2; j++)
        {
            dp[i][j] = inf;
        }
    }
    for(ll i=1; i<=n; i++)
    {
        L[i][0] = lower_bound(a.begin()+1,a.end(), a[i] - w + 1) - a.begin();
        L[i][1] = lower_bound(a.begin()+1,a.end(), a[i] - 2 * w + 1) - a.begin();
    }
    for(ll i=0; i<=P; i++)  dp[0][i] = 0;

    for(ll i=1; i<=n; i++)
    {
        for(ll p=0; p<=P; p++)
        {
            dp[i][p] = min((p > 0 ? dp[L[i][0] - 1][p - 1] : inf), dp[L[i][1] - 1][p] + 1);

        }
    }
    return dp[n][P] <= Q;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> P >> Q;
    P = min(P, n);
    Q = min(Q, n);
    a.resize(n + 1);
    for(ll i=1; i<=n; i++) cin >> a[i];
    sort(a.begin()+1,a.end());
    ll l = 1, r = inf, ans = 0;
    while (l <= r)
    {
        int m = (l + r) >> 1;
        if (check(m))
        {
            ans = m, r = m - 1;
        }
        else l = m + 1;
    }
    cout << ans;
    return 0;
}

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