oj.uz

Submission #909661

# Submission time Handle Problem Language Result Execution time Memory
909661 2024-01-17T10:24:58 Z schzeey Watching (JOI13_watching) C++14
100 / 100
 648 ms 30436 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b;
vector <int> arr;
bool check(int ans){
    vector<vector<int>> dp(n+1, vector<int>(a+1, 0));
    arr[0] = ans*-1;
    for (int i = 1; i <= n; ++i){
        //int pa = i, pb = i;
        //do pa--; while(pa != 0 && arr[i]-arr[pa] < ans);
        //do pb--; while(pb != 0 && arr[i]-arr[pb] < 2*ans);
        int pa = 0, pb = 0;
        while (pa+1 < i && arr[i]-arr[pa+1] >= ans) pa++;
        while (pb+1 < i && arr[i]-arr[pb+1] >= 2*ans) pb++;
        for (int j = 0; j < a+1; ++j){
            if (j == 0) dp[i][j] = dp[pb][j]+1;
            else dp[i][j] = min(dp[pb][j]+1, dp[pa][j-1]);
        }
    }
    return *min_element(dp[n].begin(), dp[n].end()) <= b;
}

int32_t main(){
    cin >> n >> a >> b;
    arr.resize(n+1);
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    if (a+b >= n) return cout<<1, 0;
    sort(arr.begin(), arr.end());
    //for (auto e: arr) cout << e << " ";
    int lf = 0, ri = 1e9+128;
    while (lf <= ri){
        int mid = (lf+ri)/2;
        //cout << mid << " ";
        if (check(mid)) ri = mid-1;
        else lf = mid+1;
    }
    cout << lf;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 348 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 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 59 ms 604 KB Output is correct
8 Correct 85 ms 2512 KB Output is correct
9 Correct 257 ms 12428 KB Output is correct
10 Correct 648 ms 30436 KB Output is correct
11 Correct 79 ms 1900 KB Output is correct
12 Correct 328 ms 15960 KB Output is correct
13 Correct 54 ms 604 KB Output is correct
14 Correct 63 ms 1072 KB Output is correct
15 Correct 64 ms 772 KB Output is correct