Submission #772005

#	Time	Username	Problem	Language	Result	Execution time	Memory
772005		aaron_dcoder	Watching (JOI13_watching)	C++17	100 / 100	128 ms	30164 KiB

watching

//todo
//ajihuwi


#define NDEBUG
#include <bits/stdc++.h>

using namespace std;
using ll = long long; 
//#define dbg(TXTMSG) cerr << "\n" << TXTMSG
//#define dbgv(VARN) cerr << "\n" << #VARN << " = "<<VARN << ", line: " << __LINE__ << "\n"


ll N, P/*small*/, Q/*big*/;
vector<ll> A;
vector<ll> covered_prefix_2w;
vector<ll> covered_prefix_w;



//constexpr ll MAX_N = 2002;
//constexpr ll MAX_CAMERA = MAX_N;

vector<vector<ll>> dp;

bool is_cam_placement_possible(ll w) {
    ll w2_before_indice = 0;
    ll w_before_indice = 0;
    for (ll i = 0; i < N; i++) {
        while (A[w_before_indice] <= (A[i]-w)) {
            w_before_indice++;
        }
        while (A[w2_before_indice] <= (A[i]-2*w)) {
            w2_before_indice++;
        }

        covered_prefix_w[i]=w_before_indice;
        covered_prefix_2w[i]=w2_before_indice;
    }

    for (ll sectiontill = 1; sectiontill <= N; sectiontill++)
    {
        dp[sectiontill][0] = dp[covered_prefix_w[sectiontill-1]][0]+1;
   
        for (ll numbigcam = 1; numbigcam <= Q; numbigcam++)
        {
            dp[sectiontill][numbigcam] = min({
                dp[covered_prefix_2w[sectiontill-1]][numbigcam-1],
                dp[covered_prefix_w[sectiontill-1]][numbigcam]+1
            });
        } 
        if (dp[sectiontill][Q] > P) {
            return false;
        }
        if (dp[sectiontill][Q]+N-sectiontill <= P) {
            return true;
        }
    }

    return (dp[N][Q] <= P); 
}


int main() {
    cin.tie(nullptr);
    cin.sync_with_stdio(false);

    cin >> N >> P >> Q;
    A = vector<ll>(N);
    covered_prefix_2w = vector<ll>(N);
    covered_prefix_w = vector<ll>(N);
    for (ll i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    sort(A.begin(),A.end());

    if (N==0) {
        cout << "0";
        return EXIT_SUCCESS;
    }
    if (N <= (P+Q)) {
        cout << "1";
        return EXIT_SUCCESS;
    }
    

    dp.assign(N+1,vector<ll>(Q+1,0));
    

    ll max_possible_w = 1ll + (*A.crbegin())/(P+Q);
    ll min_possible_w = 1ll;

    while (max_possible_w > min_possible_w) {
        ll mid = (max_possible_w+min_possible_w)/2;
        if (is_cam_placement_possible(mid)) {
            max_possible_w = mid;
        }
        else {
            min_possible_w = mid+1;
        }
    } 

    cout << min_possible_w;

}
    
    /*
13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75*/

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