제출 #1153006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153006		sunflower	Watching (JOI13_watching)	C++17	50 / 100	587 ms	1520 KiB

watching

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define debug(x) cout << "[" << #x << " = " << (x) << "]" << endl

#define prev __prev

int numPart, smallCam, largeCam;

#define MAX_N 2'020
int a[MAX_N + 2];

namespace subtask1 {
    bool check() {
        return (numPart <= 100);
    }

    bool dp[102][102][102]; // dp[i][j][k]: có thể phủ i cái đầu tiên với j (nhỏ) và k (lớn);

    bool check(int g) {
        FOR(i, 0, numPart) FOR(j, 0, smallCam) FOR(k, 0, largeCam) {
            if (i == 0) dp[i][j][k] = true;
            else dp[i][j][k] = false;
        }

        dp[0][0][0] = true;
        FOR(i, 1, numPart) {
            FOR(j, 0, smallCam)
                FOR(k, 0, largeCam) {
                    if (j > 0) dp[i][j][k] |= dp[i][j - 1][k];
                    if (k > 0) dp[i][j][k] |= dp[i][j][k - 1];

                    // dung 1 small;
                    if (j > 0) FOR(prev, 1, i) if (a[i] - a[prev] + 1 <= g) dp[i][j][k] |= dp[prev - 1][j - 1][k];
                    // dung 1 large;
                    if (k > 0) FOR(prev, 1, i) if (a[i] - a[prev] + 1 <= 2 * g) dp[i][j][k] |= dp[prev - 1][j][k - 1];
                }
        }

        return dp[numPart][smallCam][largeCam];
    }

    void solve() {

        int l = 1, r = (int) 1e9 + 1, g, vt = -1;
        while (l <= r) {
            g = (l + r) >> 1;
            if (check(g)) vt = g, r = g - 1;
            else l = g + 1;
        }

        cout << vt;
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("test.inp","r",stdin);
    // freopen("test.out","w",stdout);
    cin >> numPart >> smallCam >> largeCam;
    FOR(i, 1, numPart) cin >> a[i];
    sort(a + 1, a + 1 + numPart);

    if (smallCam + largeCam >= numPart) return cout << 1, 0;

    if (subtask1 :: check()) return subtask1 :: solve(), 0;

    return 0;
}

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