oj.uz

Submission #503125

# Submission time Handle Problem Language Result Execution time Memory
503125 2022-01-07T10:09:58 Z colossal_pepe Watching (JOI13_watching) C++17
100 / 100
 153 ms 15200 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 320 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 244 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 13 ms 1228 KB Output is correct
9 Correct 62 ms 6232 KB Output is correct
10 Correct 153 ms 15200 KB Output is correct
11 Correct 9 ms 972 KB Output is correct
12 Correct 68 ms 8012 KB Output is correct
13 Correct 8 ms 340 KB Output is correct
14 Correct 10 ms 488 KB Output is correct
15 Correct 10 ms 460 KB Output is correct