oj.uz

Submission #771975

# Submission time Handle Problem Language Result Execution time Memory
771975 2023-07-03T13:03:36 Z aaron_dcoder Watching (JOI13_watching) C++17
0 / 100
 1000 ms 31700 KB 
//todo
//ajihuwi


//#define _GLIBCXX_DEBUG 
#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<array<ll,MAX_CAMERA>> 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;
    }

    //array<ll,MAX_CAMERA> filledarr;
    //filledarr.fill(-1);
    //dp.assign(N+1,filledarr);

    dp[0].fill(0);
    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
            });
        } 
    }

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


int main() {
    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,array<ll,MAX_CAMERA>());
    

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

    while (max_possible_w != min_possible_w) {
        ll mid = (min_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;

}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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