제출 #1324079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324079		sh_qaxxorov_571	Watching (JOI13_watching)	C++20	100 / 100	125 ms	16148 KiB

watching

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, P, Q;
int A[2005];
int dp[2005][2005]; // dp[tadbir_indeksi][ishlatilgan_kichik_kameralar] = minimal_katta_kameralar
int nextW[2005], next2W[2005];

// Berilgan w bilan barcha tadbirlarni yopish mumkinligini tekshirish
bool check(int w) {
    if (P >= N || Q >= N) return true; // Agar kameralar tadbirlardan ko'p bo'lsa

    // Oldindan har bir tadbir uchun kameralar qayergacha yetishini hisoblab chiqamiz
    for (int i = 0; i < N; i++) {
        nextW[i] = lower_bound(A, A + N, A[i] + w) - A;
        next2W[i] = lower_bound(A, A + N, A[i] + 2 * w) - A;
    }

    // DP jadvalini cheksizlik bilan to'ldiramiz
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= P; j++) dp[i][j] = Q + 1;
    }

    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= P; j++) {
            if (dp[i][j] > Q) continue;

            // 1. Kichik kamera ishlatish
            if (j + 1 <= P) {
                dp[nextW[i]][j + 1] = min(dp[nextW[i]][j + 1], dp[i][j]);
            }

            // 2. Katta kamera ishlatish
            dp[next2W[i]][j] = min(dp[next2W[i]][j], dp[i][j] + 1);
        }
    }

    // Oxirgi tadbirdan keyin birorta holatda katta kameralar soni Q dan oshmasa - true
    for (int j = 0; j <= P; j++) {
        if (dp[N][j] <= Q) return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> P >> Q;
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A, A + N);

    // Ikkilik qidiruv (Binary Search)
    int low = 1, high = 1000000000, ans = 1000000000;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

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