oj.uz

Submission #901304

# Submission time Handle Problem Language Result Execution time Memory
901304 2024-01-09T10:10:23 Z KienTran Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16208 KB 
#include <bits/stdc++.h>

using namespace std;

const int O = 2e3 + 5;
const int base = 500;
const int mod = 998244353;

int n, p, q, a[O], f[O][O];

bool check(int mid){
    f[0][0] = 0;
    for (int i = 1; i <= n; ++ i){
        for (int j = 0; j <= min(i, q); ++ j){
            f[i][j] = 1e9;
            int id = lower_bound(a + 1, a + n + 1, a[i] - 2 * mid + 1) - a - 1;
            if (j) f[i][j] = min(f[i][j], f[id][j - 1]);

            id = lower_bound(a + 1, a + n + 1, a[i] - mid + 1) - a - 1;
            f[i][j] = min(f[i][j], f[id][j] + 1);
        }
    }

    return f[n][q] <= p;
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> p >> q;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    sort(a + 1, a + n + 1);
    //for (int i = 1; i <= n; ++ i) cout << a[i] << " "; cout << endl;

    if (p + q >= n) return cout << 1, 0;

    int l = 0, r = 1e9;
    while (l <= r){
        int mid = (l + r) / 2;
        if (check(mid)) r = mid - 1;
        else l = mid + 1;
    }

    cout << l;
}

Compilation message

watching.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main(){
      | ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4 ms 2520 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15452 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 28 ms 15452 KB Output is correct
8 Correct 939 ms 15948 KB Output is correct
9 Correct 208 ms 15576 KB Output is correct
10 Correct 139 ms 15452 KB Output is correct
11 Execution timed out 1016 ms 16208 KB Time limit exceeded
12 Halted 0 ms 0 KB -