Submission #1291844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291844		chf	Watching (JOI13_watching)	C++20	100 / 100	246 ms	16192 KiB

watching

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, P, Q;
    cin >> N >> P >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    int n = A.size();
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    int low = 1;
    int high = 1000000000;
    int ans = high;
    
    while (low <= high) {
        int w = low + (high - low) / 2;
        
        vector<int> small_cover(n), large_cover(n);
        for (int i = 0; i < n; i++) {
            long long end_small = (long long)A[i] + w - 1;
            auto it_small = upper_bound(A.begin(), A.end(), end_small);
            small_cover[i] = it_small - A.begin() - 1;
            
            long long end_large = (long long)A[i] + 2 * w - 1;
            auto it_large = upper_bound(A.begin(), A.end(), end_large);
            large_cover[i] = it_large - A.begin() - 1;
        }
        
        int max_j = min(n, Q);
        vector<vector<int>> dp(n + 1, vector<int>(max_j + 1, INT_MAX / 2));
        dp[0][0] = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= max_j; j++) {
                if (dp[i][j] == INT_MAX / 2) continue;
                
                int next_small = small_cover[i] + 1;
                if (next_small <= n) {
                    dp[next_small][j] = min(dp[next_small][j], dp[i][j] + 1);
                }
                
                if (j < max_j) {
                    int next_large = large_cover[i] + 1;
                    if (next_large <= n) {
                        dp[next_large][j + 1] = min(dp[next_large][j + 1], dp[i][j]);
                    }
                }
            }
        }
        
        bool possible = false;
        for (int j = 0; j <= max_j; j++) {
            if (dp[n][j] <= P) {
                possible = true;
                break;
            }
        }
        
        if (possible) {
            ans = w;
            high = w - 1;
        } else {
            low = w + 1;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

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