oj.uz

Submission #41093

# Submission time Handle Problem Language Result Execution time Memory
41093 2018-02-12T16:08:18 Z DoanPhuDuc Watching (JOI13_watching) C++
100 / 100
 195 ms 16760 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16092 KB Output is correct
2 Correct 40 ms 16268 KB Output is correct
3 Correct 40 ms 16304 KB Output is correct
4 Correct 43 ms 16380 KB Output is correct
5 Correct 48 ms 16380 KB Output is correct
6 Correct 44 ms 16380 KB Output is correct
7 Correct 45 ms 16492 KB Output is correct
8 Correct 44 ms 16492 KB Output is correct
9 Correct 42 ms 16492 KB Output is correct
10 Correct 41 ms 16528 KB Output is correct
11 Correct 44 ms 16528 KB Output is correct
12 Correct 40 ms 16528 KB Output is correct
13 Correct 42 ms 16528 KB Output is correct
14 Correct 39 ms 16528 KB Output is correct
15 Correct 47 ms 16548 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16552 KB Output is correct
2 Correct 40 ms 16552 KB Output is correct
3 Correct 166 ms 16580 KB Output is correct
4 Correct 190 ms 16580 KB Output is correct
5 Correct 60 ms 16580 KB Output is correct
6 Correct 195 ms 16580 KB Output is correct
7 Correct 46 ms 16672 KB Output is correct
8 Correct 64 ms 16672 KB Output is correct
9 Correct 107 ms 16700 KB Output is correct
10 Correct 181 ms 16700 KB Output is correct
11 Correct 62 ms 16700 KB Output is correct
12 Correct 151 ms 16760 KB Output is correct
13 Correct 46 ms 16760 KB Output is correct
14 Correct 51 ms 16760 KB Output is correct
15 Correct 44 ms 16760 KB Output is correct