Submission #282212

#	Time	Username	Problem	Language	Result	Execution time	Memory
282212		jainbot27	Watching (JOI13_watching)	C++17	100 / 100	495 ms	16404 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, p, q;
    cin >> n >> p >> q;
    if(p + q >= n) {
        cout <<"1\n";
        return 0;
    }
    vector<int> a(n);
    for(int&A:a) cin >> A;
    sort(a.begin(), a.end());
    int lo = 1, hi = 1e9;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -(1)));
        vector<int> P(n + 1), Q(n + 1);
        //cerr << "HERE\n";
        for(int i=0; i < n; i++){
            P[i] = (lower_bound(a.begin(), a.end(), a[i] + mid) - a.begin()) - i;
            //cerr << "P " << P[i] << endl;
        }
        for(int i=0; i < n; i++){
            Q[i] = (lower_bound(a.begin(), a.end(), a[i] + mid * 2) - a.begin()) - i;
            //cerr << "Q " << Q[i] << endl;
        }
        dp[0][0] = 0;
        bool good = 0;
        for(int i=0; i <= p; i++){
            for(int j=0; j <= q; j++){
                if(dp[i][j] == n){
                    good = 1;
                }
                if(dp[i][j] != -1 || (i == 0 && j == 0)){
                    dp[i + 1][j] = max(dp[i+1][j], P[dp[i][j]] + dp[i][j]);
                    dp[i][j + 1] = max(dp[i][j + 1], Q[dp[i][j]] + dp[i][j]);
                }
                //cerr << "(" << i << "," << j << ") " << dp[i][j] << endl;
            }
        }
        if(good){
            hi = mid - 1;
        }
        else{
            lo = mid + 1;
        }
    }
    cout << lo << endl;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50