oj.uz

Submission #37832

# Submission time Handle Problem Language Result Execution time Memory
37832 2017-12-28T08:39:39 Z nickyrio Watching (JOI13_watching) C++14
100 / 100
 313 ms 18120 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 2020
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;

int n, p, q, dp[N][N], a[N];
//dp[i][j] : Minimun the large camera used when fill from 1..i, used j small camera

bool ok(int w) {
    FOR(i, 0, n) FOR(j, 0, p) dp[i][j] = 1e9;
    dp[0][0] = 0;
    FOR(i, 1, n) {
        int psmall = lower_bound(a + 1, a + n + 1, a[i] - w + 1) - a - 1;
        int plarge = lower_bound(a + 1, a + n + 1, a[i] - w - w + 1) - a - 1;
        dp[i][0] = dp[plarge][0] + 1;
        FOR(j, 1, p) {
            dp[i][j] = min(dp[psmall][j - 1], dp[plarge][j] + 1);
        }
    }
    FOR(j, 0, p) if(dp[n][j] <= q) return true;
    return false;
}

int main() {
    IO; ios :: sync_with_stdio(false);
    cin >> n >> p >> q;
    p = min(p, n);
    FOR(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 0, r = 1e9, cur = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (ok(m)) {
            cur = m;
            r = m - 1;
        } else l = m + 1;
    }
    cout << cur;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18120 KB Output is correct
2 Correct 0 ms 18120 KB Output is correct
3 Correct 249 ms 18120 KB Output is correct
4 Correct 313 ms 18120 KB Output is correct
5 Correct 33 ms 18120 KB Output is correct
6 Correct 273 ms 18120 KB Output is correct
7 Correct 6 ms 18120 KB Output is correct
8 Correct 23 ms 18120 KB Output is correct
9 Correct 103 ms 18120 KB Output is correct
10 Correct 263 ms 18120 KB Output is correct
11 Correct 19 ms 18120 KB Output is correct
12 Correct 123 ms 18120 KB Output is correct
13 Correct 9 ms 18120 KB Output is correct
14 Correct 9 ms 18120 KB Output is correct
15 Correct 9 ms 18120 KB Output is correct