제출 #1251734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251734		MisterReaper	Watching (JOI13_watching)	C++20	100 / 100	736 ms	15940 KiB

watching

// File C.cpp created on 03.08.2025 at 14:29:34
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

bool chmax(int& a, int b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

    int N, P, Q;
    std::cin >> N >> P >> Q;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::sort(A.begin(), A.end());

    P = std::min(P, N);
    Q = std::min(Q, N);

    std::vector<std::vector<int>> f;
    auto check = [&](int w) -> int {
        f.assign(P + 1, std::vector<int>(Q + 1));
        for (int i = 0; i <= P; ++i) {
            for (int j = 0; j <= Q; ++j) {
                if (f[i][j] == N) {
                    return true;
                }
                int x = f[i][j];
                if (i != P) {
                    int y = int(std::lower_bound(A.begin(), A.end(), A[x] + w) - A.begin());
                    chmax(f[i + 1][j], y);
                }
                if (j != Q) {
                    int y = int(std::lower_bound(A.begin(), A.end(), A[x] + 2 * w) - A.begin());
                    chmax(f[i][j + 1], y);
                }
            }
        }
        return false;
    };

    int lo = 1, hi = A.back();
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            hi = mid; 
        } else {
            lo = mid + 1;
        }
    }

    std::cout << lo << '\n';

    return 0;
}

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