Submission #958348

#	Time	Username	Problem	Language	Result	Execution time	Memory
958348		JwFXoiz	Watching (JOI13_watching)	C++14	100 / 100	570 ms	31432 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

const int MXN = 2e3 + 5;

int n, p, q;
int a[MXN];
int dp[MXN][MXN];

int need(int val)
{
    for (int i = 0; i <= p; i++) 
    {
        int k1 = 0, k2 = 0;
        for (int j = 1; j <= n; j++) 
        {
            dp[i][j] = inf;
            while (k1 + 1 <= n && a[k1 + 1] <= a[j] - val) k1++;
            while (k2 + 1 <= n && a[k2 + 1] <= a[j] - 2 * val) k2++;
            dp[i][j] = dp[i][k2] + 1;
            if (i) dp[i][j] = min(dp[i][j], dp[i - 1][k1]);
        }
    }
    return dp[p][n];
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> p >> q;
    if (p >= n || q >= n)
    {
        cout << 1 << '\n';
        return 0;
    }
    p = min(p, n), q = min(q, n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (need(mid) > q) l = mid + 1;
        else r = mid;
    }
    cout << l << '\n';
}

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