oj.uz

Submission #772005

# Submission time Handle Problem Language Result Execution time Memory
772005 2023-07-03T13:49:06 Z aaron_dcoder Watching (JOI13_watching) C++17
100 / 100
 128 ms 30164 KB 
//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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 55 ms 12268 KB Output is correct
9 Correct 10 ms 2308 KB Output is correct
10 Correct 3 ms 1748 KB Output is correct
11 Correct 128 ms 30164 KB Output is correct
12 Correct 44 ms 15700 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 628 KB Output is correct