oj.uz

Submission #40349

# Submission time Handle Problem Language Result Execution time Memory
40349 2018-01-31T08:48:34 Z krauch Watching (JOI13_watching) C++14
100 / 100
 172 ms 9192 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

const ll ool = 1e18 + 9;
const int N = 3e3 + 3, oo = 1e9 + 9;

int n, P, Q, a[N], d[N][N];

bool check(int W) {
    int ptr = 1;
    forn(i, 0, P) forn(j, 0, Q) d[i][j] = 1;
    forn(i, 0, P) {
        forn(j, 0, Q) {
            if (d[i][j] == -1) continue;
            int ptr = d[i][j];
            while (ptr <= n && a[ptr] - a[d[i][j]] + 1 <= W) {
                ++ptr;
            }
            d[i + 1][j] = max(d[i + 1][j], ptr);
            while (ptr <= n && a[ptr] - a[d[i][j]] + 1 <= 2 * W) {
                ++ptr;
            }
            d[i][j + 1] = max(d[i][j + 1], ptr);
        }
    }
    return (d[P][Q] == n + 1);
}

int main() {

    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n >> P >> Q;
    Q = min(Q, n);
    P = min(P, n - Q);
    forn(i, 1, n) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    int l = 1, r = a[n];
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << "\n";

    return 0;
}

Compilation message

watching.cpp: In function 'bool check(int)':
watching.cpp:23:9: warning: unused variable 'ptr' [-Wunused-variable]
     int ptr = 1;
         ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 800 KB Output is correct
5 Correct 1 ms 800 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 1 ms 800 KB Output is correct
9 Correct 2 ms 800 KB Output is correct
10 Correct 2 ms 800 KB Output is correct
11 Correct 2 ms 908 KB Output is correct
12 Correct 2 ms 908 KB Output is correct
13 Correct 1 ms 908 KB Output is correct
14 Correct 1 ms 908 KB Output is correct
15 Correct 1 ms 908 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 908 KB Output is correct
2 Correct 2 ms 908 KB Output is correct
3 Correct 128 ms 5688 KB Output is correct
4 Correct 38 ms 9056 KB Output is correct
5 Correct 3 ms 9056 KB Output is correct
6 Correct 3 ms 9056 KB Output is correct
7 Correct 3 ms 9056 KB Output is correct
8 Correct 26 ms 9056 KB Output is correct
9 Correct 30 ms 9056 KB Output is correct
10 Correct 42 ms 9192 KB Output is correct
11 Correct 33 ms 9192 KB Output is correct
12 Correct 172 ms 9192 KB Output is correct
13 Correct 3 ms 9192 KB Output is correct
14 Correct 3 ms 9192 KB Output is correct
15 Correct 3 ms 9192 KB Output is correct