oj.uz

Submission #894603

# Submission time Handle Problem Language Result Execution time Memory
894603 2023-12-28T14:18:51 Z IWKR Watching (JOI13_watching) C++17
50 / 100
 1000 ms 32084 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int dp[2001][2001];
vector<int> v;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, p, q;
    cin >> n >> p >> q;
    if (p + q >= n) {
        cout << 1;
        return 0;
    }
    int low = 0;
    int high = 0;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
        high = max(high, a);
    }
    sort(v.begin(), v.end());
    while (high - low > 1) {
        memset(dp, 0, sizeof dp);
        int mid = (high + low) / 2;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= p; j++) {
                int a = upper_bound(v.begin(), v.end(), v[i] + 2 * mid - 1) - v.begin();
                dp[i][j] = dp[a][j] + 1;
                if (j != 0) {
                    int b = upper_bound(v.begin(), v.end(), v[i] + mid - 1) - v.begin();
                    dp[i][j] = min(dp[i][j], dp[b][j - 1]);
                }
            }
        }
        int ans = LLONG_MAX;
        for (int i = 0; i <= p; i++) {
            ans = min(ans, dp[0][i]);
        }
        if (ans <= q) {
            high = mid;
        } else {
            low = mid;
        }
    }
    cout << high;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 31580 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 61 ms 31576 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 66 ms 31784 KB Output is correct
8 Correct 63 ms 31580 KB Output is correct
9 Correct 61 ms 31788 KB Output is correct
10 Correct 61 ms 31784 KB Output is correct
11 Correct 64 ms 31576 KB Output is correct
12 Correct 64 ms 31576 KB Output is correct
13 Correct 61 ms 31700 KB Output is correct
14 Correct 60 ms 31580 KB Output is correct
15 Correct 61 ms 31784 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 32084 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 85 ms 31836 KB Output is correct
8 Correct 226 ms 31836 KB Output is correct
9 Execution timed out 1006 ms 31828 KB Time limit exceeded
10 Halted 0 ms 0 KB -