Submission #1272533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272533		dang_hai_long	Watching (JOI13_watching)	C++20	100 / 100	244 ms	16256 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    int P, Q;
    cin >> N >> P >> Q;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end());

    auto can = [&](long long w)->bool{
        vector<int> r1(N), r2(N);
        int p1 = 0, p2 = 0;
        for (int i = 0; i < N; ++i){
            if (p1 < i) p1 = i;
            while (p1+1 < N && A[p1+1] <= A[i] + w - 1) ++p1;
            r1[i] = p1;
            if (p2 < i) p2 = i;
            while (p2+1 < N && A[p2+1] <= A[i] + 2*w - 1) ++p2;
            r2[i] = p2;
        }

        int maxSmall = min(P, N);
        vector< vector<int> > dp(N+1, vector<int>(maxSmall+1, INF));
        dp[0][0] = 0;

        for (int i = 0; i < N; ++i){
            for (int used = 0; used <= maxSmall; ++used){
                int curLarge = dp[i][used];
                if (curLarge == INF) continue;
                // use small if possible
                if (used < maxSmall){
                    int to = r1[i] + 1;
                    if (dp[to][used+1] > curLarge) dp[to][used+1] = curLarge;
                }
                int to2 = r2[i] + 1;
                if (dp[to2][used] > curLarge + 1) dp[to2][used] = curLarge + 1;
            }
        }

        for (int used = 0; used <= maxSmall; ++used){
            if (dp[N][used] <= Q) return true;
        }
        return false;
    };

    long long lo = 1, hi = 1000000000LL, ans = hi;
    while (lo <= hi){
        long long mid = (lo + hi) >> 1;
        if (can(mid)){
            ans = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }

    cout << ans << "\n";
    return 0;
}

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