Submission #1153013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153013		sunflower	Watching (JOI13_watching)	C++17	100 / 100	569 ms	16288 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

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

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;
    }
}

namespace subtask2 {
    // dp[i][j]: so luong largeCam it nhat can de phu doan tu 1 .. i, voi j smallCam;
    const int inf = (int) 1e9 + 7;

    int dp[MAX_N + 2][MAX_N + 2];

    bool check(int w) {
        FOR(i, 0, numPart) FOR(j, 0, smallCam) {
            if (i == 0) dp[i][j] = 0;
            else dp[i][j] = inf;
        }

        dp[0][0] = 0;
        FOR(j, 0, smallCam) {
            int sma = 1, lar = 1;
            FOR(i, 1, numPart) {
                // be careful with j = 0;
                if (j > 0) dp[i][j] = dp[i][j - 1];

                // dung small;
                if (j > 0) {
                    while (a[i] - a[sma] + 1 > w) ++sma;
                    minimize(dp[i][j], dp[sma - 1][j - 1]);
                }
                // dung large;
                while (a[i] - a[lar] + 1 > 2 * w) ++lar;
                minimize(dp[i][j], dp[lar - 1][j] + 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);
    if (fopen("test.inp","r")) {
        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;
    subtask2 :: solve();

    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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