Submission #945271

#	Time	Username	Problem	Language	Result	Execution time	Memory
945271		mariamp1	Watching (JOI13_watching)	C++14	100 / 100	162 ms	16236 KiB

watching

#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;
        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;

        for(int j = 0; j <= i; j++){
            ///             a[i]-mid+1     a[i]
            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 / 50
• Subtask 2: 50 / 50