oj.uz

Submission #945269

# Submission time Handle Problem Language Result Execution time Memory
945269 2024-03-13T15:33:40 Z mariamp1 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16208 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int N = 2000 + 5;
int n, p, q;
int a[N];
set<pair<int, int>> st;
int dp[N][N];
bool check(int mid){
    for(int i = 1; i <= n; i++){
        for (int j = 0; j <= n; j++) dp[i][j] = 1e9;
        for(int j = 0; j <= i; j++){
            ///             a[i]-mid+1     a[i]
            auto it = st.lower_bound({a[i] - mid + 1, 0});
            it--; int l1 = (*it).second;
            auto it1 = st.lower_bound({a[i] - 2 * mid + 1, 0});
            it1--; int l2 = (*it1).second;
            if (j == 0) dp[i][j] = dp[l2][j] + 1;
            else dp[i][j] = min(dp[l1][j - 1], dp[l2][j] + 1);
            if (i == n && j <= p && dp[i][j] <= q) return 1;
        }
    }
    return 0;
}
int main(){
    cin >> n >> p >> q;
    p = min(p, n);
    q = min(q, n);
    st.insert({-1e9, 0});
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        st.insert({a[i], i});
    }
    int l = 1, r = 1e9;
    int ans = 0;
    while(l <= r){
        int mid = l + (r-l)/2;
        if(check(mid)){
            r = mid-1;
            ans = mid;
        }else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2648 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 4 ms 2600 KB Output is correct
6 Correct 4 ms 2396 KB Output is correct
7 Correct 4 ms 2396 KB Output is correct
8 Correct 4 ms 2396 KB Output is correct
9 Correct 4 ms 2396 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 4 ms 2396 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 4 ms 2392 KB Output is correct
14 Correct 4 ms 2500 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 16208 KB Time limit exceeded
2 Halted 0 ms 0 KB -