oj.uz

Submission #946587

# Submission time Handle Problem Language Result Execution time Memory
946587 2024-03-14T19:08:02 Z VMaksimoski008 Watching (JOI13_watching) C++14
100 / 100
 176 ms 16336 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

vector<vector<int> > dp(2005, vector<int>(2005, 1e9));

int main() {
    int n, p, q;
    cin >> n >> p >> q;

    p = min(n, p);
    q = min(n, q);

    vector<int> v(n+1, -1e9);
    for(int i=1; i<=n; i++) cin >> v[i];
    sort(1+all(v));

    auto f = [&](int mid) {
        for(int i=0; i<=n; i++)
            for(int j=0; j<=p; j++) dp[i][j] = 1e9;
        dp[0][0] = 0;

        int k=0, l=0;
        for(int i=1; i<=n; i++) {
            while(v[i] - v[k] >= mid) k++;
            while(v[i] - v[l] >= 2ll * mid) l++;
            for(int j=0; j<=p; j++) {
                if(j) dp[i][j] = dp[k-1][j-1];
                dp[i][j] = min(dp[i][j], dp[l-1][j] + 1);
            }
        }

        for(int i=0; i<=p; i++)
            if(dp[n][i] <= q) return 1;
        return 0;
    };

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

    cout << ans << '\n';
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16216 KB Output is correct
2 Correct 7 ms 16220 KB Output is correct
3 Correct 8 ms 16224 KB Output is correct
4 Correct 9 ms 16220 KB Output is correct
5 Correct 8 ms 16000 KB Output is correct
6 Correct 8 ms 16216 KB Output is correct
7 Correct 8 ms 16220 KB Output is correct
8 Correct 8 ms 16220 KB Output is correct
9 Correct 9 ms 16220 KB Output is correct
10 Correct 8 ms 16216 KB Output is correct
11 Correct 8 ms 16220 KB Output is correct
12 Correct 8 ms 16220 KB Output is correct
13 Correct 7 ms 16220 KB Output is correct
14 Correct 8 ms 16220 KB Output is correct
15 Correct 9 ms 16240 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16220 KB Output is correct
2 Correct 7 ms 16244 KB Output is correct
3 Correct 151 ms 16220 KB Output is correct
4 Correct 171 ms 16244 KB Output is correct
5 Correct 16 ms 16220 KB Output is correct
6 Correct 169 ms 16220 KB Output is correct
7 Correct 10 ms 16220 KB Output is correct
8 Correct 21 ms 16220 KB Output is correct
9 Correct 75 ms 16220 KB Output is correct
10 Correct 176 ms 16240 KB Output is correct
11 Correct 17 ms 16220 KB Output is correct
12 Correct 92 ms 16220 KB Output is correct
13 Correct 10 ms 16220 KB Output is correct
14 Correct 11 ms 16336 KB Output is correct
15 Correct 11 ms 16276 KB Output is correct