Submission #1309282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309282		bobothenubchick	Watching (JOI13_watching)	C++20	0 / 100	54 ms	15844 KiB

watching

# include <bits/stdc++.h>
using namespace std;
int n,p,q,a[2005],dp[2005][100005];

bool check(int w)
{
    for (int i =0; i <= n; i++)
    {
        for (int j = 0; j <= q; j++)
        {
            dp[i][j] = 1e9;
        }
    }
    dp[0][0] = 0;
    int j = 1, k = 1;
    for (int i = 1; i <= n; i++)
    {   
        while (j <= i and a[i]-a[j]+1 > w)
        {
            j++;
        }
        while (k <= i and a[i]-a[k]+1 > w*2)
        {
            k++;
        }
        for (int t = 0; t <= p; t++)
        {
            if (t > 0) dp[i][t] = min(dp[i][t],dp[j-1][t-1]);
            dp[i][t] = min(dp[i][t],dp[k-1][t]+1);
        }
    }
    bool checky = false;
    for (int i = 0; i <= p; i++)
    {
        // cerr << dp[n][i] << " ";
        if (dp[n][i] <= q) checky = true;
    }
    return checky;
}

int bs()
{
    int l = 1, r = a[n], mid;
    while (l <= r )
    {
        mid = (l+r)/2;
        if (check(mid)) r = mid-1;
        else l = mid+1;
    }
    return l;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (p+q >= n)
    {
        cout << 1;
        return 0;
    }
    sort(a+1,a+n+1);
    cout << bs();
    // cout << check(3);
}

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