Submission #503125

#	Time	Username	Problem	Language	Result	Execution time	Memory
503125		colossal_pepe	Watching (JOI13_watching)	C++17	100 / 100	153 ms	15200 KiB

watching

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define calcdp for (int i = n - 1; i >= 0; i--) { int useq = lower_bound(a, a + n, a[i] + (2 * w)) - a; int usep = lower_bound(a, a + n, a[i] + w) - a; dp[i][0] = dp[useq][0] + 1; for (int j = 1; j <= p; j++) { dp[i][j] = min(dp[useq][j] + 1, dp[usep][j - 1]); } }
 
int n, p, q, a[2005];

int solve() {
    int dp[n + 1][p + 1];
    for (int i = 0; i <= p; i++) {
        dp[n][i] = 0;
    }
    int minw = 1, maxw = 1e9;
    while (maxw - minw >= 2) {
        int w = (maxw + minw) / 2;
        /*
        for (int i = n - 1; i >= 0; i--) {
            int useq = lower_bound(a, a + n, a[i] + (2 * w)) - a;
            int usep = lower_bound(a, a + n, a[i] + w) - a;
            dp[i][0] = dp[useq][0] + 1;
            for (int j = 1; j <= p; j++) {
                dp[i][j] = min(dp[useq][j] + 1, dp[usep][j - 1]);
            }
        }
        */
       calcdp;
       if (dp[0][p] <= q) maxw = w;
       else minw = w + 1;
    }
    for (int w = minw; w <= maxw; w++) {
        calcdp;
        if (dp[0][p] <= q) return w;
    }
    return 1e9;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> p >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    cout << (p + q < n ? solve() : 1) << '\n';
    return 0;
}

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