oj.uz

Submission #745514

# Submission time Handle Problem Language Result Execution time Memory
745514 2023-05-20T09:26:02 Z sleepntsheep Watching (JOI13_watching) C++17
100 / 100
 226 ms 16084 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;

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

int ok(int w) {
    memset(dp, 63, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        auto ip = max(0l, upper_bound(a, a+i, a[i] - w) - a - 1);
        auto iq = max(0l, upper_bound(a, a+i, a[i] - 2*w) - a - 1);
        for (int j = 0; j <= p; ++j) {
            if (j) {
                dp[i][j] = min(dp[i][j], dp[ip][j-1]);
            }
            dp[i][j] = min(dp[i][j], dp[iq][j] + 1);
        }
    }
    for (int j = 0; j <= p; ++j)
        if (dp[n][j] <= q) return 1;
    return 0;
}

int main() {
    scanf("%d%d%d", &n, &p, &q);
    p = min(p, n); q = min(q, n);
    for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    sort(a+1, a+n+1);

    int l = 0, r = 1e9+2;
    while (r - l > 1) {
        auto m = (l+r)/2;
        if (ok(m)) r = m;
        else l = m;
    }
    printf("%d", r);

    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d%d", &n, &p, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:29:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for (int i = 1; i <= n; ++i) scanf("%d", a+i);
      |                                  ~~~~~^~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 16084 KB Output is correct
2 Correct 53 ms 15940 KB Output is correct
3 Correct 56 ms 15956 KB Output is correct
4 Correct 52 ms 16020 KB Output is correct
5 Correct 50 ms 15956 KB Output is correct
6 Correct 55 ms 16020 KB Output is correct
7 Correct 55 ms 16020 KB Output is correct
8 Correct 54 ms 16024 KB Output is correct
9 Correct 58 ms 16020 KB Output is correct
10 Correct 57 ms 16020 KB Output is correct
11 Correct 55 ms 16020 KB Output is correct
12 Correct 57 ms 15916 KB Output is correct
13 Correct 53 ms 15956 KB Output is correct
14 Correct 55 ms 15956 KB Output is correct
15 Correct 54 ms 16016 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16024 KB Output is correct
2 Correct 55 ms 15956 KB Output is correct
3 Correct 189 ms 16044 KB Output is correct
4 Correct 220 ms 16036 KB Output is correct
5 Correct 64 ms 15956 KB Output is correct
6 Correct 226 ms 16040 KB Output is correct
7 Correct 59 ms 16036 KB Output is correct
8 Correct 70 ms 16040 KB Output is correct
9 Correct 123 ms 16036 KB Output is correct
10 Correct 218 ms 16036 KB Output is correct
11 Correct 69 ms 16040 KB Output is correct
12 Correct 152 ms 16044 KB Output is correct
13 Correct 58 ms 16040 KB Output is correct
14 Correct 58 ms 16048 KB Output is correct
15 Correct 60 ms 15956 KB Output is correct