제출 #1291832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291832		chf	Watching (JOI13_watching)	C++20	0 / 100	198 ms	327680 KiB

watching

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

using namespace std;

bool canCover(int w, const vector<int>& events, int P, int Q) {
    int n = events.size();
    
    // Precompute coverage for each starting position
    vector<int> smallCover(n), largeCover(n);
    for (int i = 0; i < n; i++) {
        // Small camera coverage from position i
        int j = i;
        while (j < n && events[j] <= events[i] + w - 1) j++;
        smallCover[i] = j - 1;
        
        // Large camera coverage from position i  
        j = i;
        while (j < n && events[j] <= events[i] + 2 * w - 1) j++;
        largeCover[i] = j - 1;
    }
    
    // DP state: dp[i][j] = min small cameras needed to cover first i events with j large cameras
    vector<vector<int>> dp(n + 1, vector<int>(Q + 1, INT_MAX / 2));
    dp[0][0] = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= Q; j++) {
            if (dp[i][j] == INT_MAX / 2) continue;
            
            // Use small camera at current position
            int nextSmall = smallCover[i] + 1;
            if (nextSmall <= n) {
                dp[nextSmall][j] = min(dp[nextSmall][j], dp[i][j] + 1);
            }
            
            // Use large camera at current position
            int nextLarge = largeCover[i] + 1;
            if (j < Q && nextLarge <= n) {
                dp[nextLarge][j + 1] = min(dp[nextLarge][j + 1], dp[i][j]);
            }
        }
    }
    
    // Check if we can cover all events
    for (int j = 0; j <= Q; j++) {
        if (dp[n][j] <= P) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, P, Q;
    cin >> N >> P >> Q;
    
    vector<int> events(N);
    for (int i = 0; i < N; i++) {
        cin >> events[i];
    }
    
    // Sort and remove duplicates
    sort(events.begin(), events.end());
    events.erase(unique(events.begin(), events.end()), events.end());
    int n = events.size();
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    // Binary search for minimum w
    int left = 1;
    int right = events.back() - events[0];
    int answer = right;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (canCover(mid, events, P, Q)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

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