Submission #1291831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291831		chf	Watching (JOI13_watching)	C++20	0 / 100	207 ms	327680 KiB

watching

#include<bits/stdc++.h>

using namespace std;

bool canCover(int w, const vector<int>& events, int P, int Q) {
    int n = events.size();
    
    vector<int> smallCover(n), largeCover(n);
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && events[j] <= events[i] + w - 1) j++;
        smallCover[i] = j - 1;
        
        j = i;
        while (j < n && events[j] <= events[i] + 2 * w - 1) j++;
        largeCover[i] = j - 1;
    }
    
    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;
            
            int nextSmall = smallCover[i] + 1;
            if (nextSmall <= n) {
                dp[nextSmall][j] = min(dp[nextSmall][j], dp[i][j] + 1);
            }
            
            int nextLarge = largeCover[i] + 1;
            if (j < Q && nextLarge <= n) {
                dp[nextLarge][j + 1] = min(dp[nextLarge][j + 1], dp[i][j]);
            }
        }
    }
    
    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(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;
    }
    
    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