Submission #41093

#	Time	Username	Problem	Language	Result	Execution time	Memory
41093		DoanPhuDuc	Watching (JOI13_watching)	C++98	100 / 100	195 ms	16760 KiB

watching

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;

int n, p, q;
int a[N];
int dp[N][N], nxt[N][2];

void Minimize(int &a, int b) {
    a = min(a, b);
}

bool Check(int m) {
    memset(dp, INF, sizeof dp);
    int p1 = 1, p2 = 1;
    FOR(i, 1, n) {
        while (p1 <= n && a[p1] - a[i] + 1 <= m) ++p1;
        while (p2 <= n && a[p2] - a[i] + 1 <= 2 * m) ++p2;
        nxt[i][0] = p1 - 1;
        nxt[i][1] = p2 - 1;
    }
    dp[0][0] = 0;
    REP(i, 0, n) {
        FOR(j, 0, min(i, p)) if (dp[i][j] != INF) {
            Minimize(dp[nxt[i + 1][0]][j + 1], dp[i][j]);
            Minimize(dp[nxt[i + 1][1]][j + 0], dp[i][j] + 1);
        }
    }
    FOR(j, 0, min(n, p)) if (dp[n][j] <= q) return true;
    return false;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d%d", &n, &p, &q);
    FOR(i, 1, n) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int l = 1, r = (int)1e9, f = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (Check(m)) {
            f = m;
            r = m - 1;
        } else l = m + 1;
    }
    printf("%d", f);
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:51:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &p, &q);
                                ^
watching.cpp:52:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^

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