oj.uz

Submission #1051803

# Submission time Handle Problem Language Result Execution time Memory
1051803 2024-08-10T09:53:14 Z fryingduc Watching (JOI13_watching) C++17
100 / 100
 340 ms 30520 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long

const int maxn = 2005;
int n, a[maxn], p, q;

bool check(int mid) {
    vector<vector<int>> f(n + 1, vector<int>(p + 2, 1e9));
    for(int i = 0; i <= p + 1; ++i) {
        f[0][i] = 0;
    }
    int pl = 0, pr = 0;
    for(int i = 1; i <= n; ++i) {
        while(pl < i and a[i] - mid + 1 > a[pl]) ++pl;
        while(pr < i and a[i] - mid * 2 + 1 > a[pr]) ++pr;
        if(a[pl] >= a[i] - mid + 1 and pl) --pl;
        if(a[pr] >= a[i] - mid * 2 + 1 and pr) --pr;
        
        for(int j = 0; j <= p; ++j) {
            f[i][j] = f[pr][j] + 1;
            if(j) f[i][j] = min(f[i][j], f[pl][j - 1]);
        }
    }
    
    int ans = 1e9;
    for(int i = 0; i <= p; ++i) {
        ans = min(ans, f[n][i]);
    }
    return ans <= q;
}
void solve() {
    cin >> n >> p >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    if(p + q >= n) {
        cout << 1 << '\n';
        return;
    }
    sort(a + 1, a + n + 1);
    int l = 0, r = 1e9, res = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
//    cerr << check(9);
    cout << res;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 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 456 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 816 KB Output is correct
8 Correct 20 ms 2604 KB Output is correct
9 Correct 120 ms 12504 KB Output is correct
10 Correct 340 ms 30520 KB Output is correct
11 Correct 18 ms 2040 KB Output is correct
12 Correct 176 ms 16076 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 6 ms 876 KB Output is correct
15 Correct 4 ms 844 KB Output is correct