oj.uz

Submission #51439

# Submission time Handle Problem Language Result Execution time Memory
51439 2018-06-18T02:25:09 Z EntityIT Watching (JOI13_watching) C++14
100 / 100
 457 ms 32252 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2005, inf = 1e18;
int n, p, q, a[N], dp[N][N];

signed main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> p >> q;
    if (p >= n || q >= n) return cout << 1, 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort (a + 1, a + n + 1);
    int l = 1, r = 1000000000;

    while (l < r) {
        int mid = (l + r) >> 1, pter1, pter2;
        pter1 = pter2 = 1;
        memset (dp, 63, sizeof dp);
        dp[0][0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= p; ++j) {
                if (dp[i][j] >= inf) continue;
                while (pter1 <= n && a[pter1] <= a[i + 1] + mid - 1) pter1++;
                dp[pter1 - 1][j + 1] = min (dp[pter1 - 1][j + 1], dp[i][j]);
                while (pter2 <= n && a[pter2] <= a[i + 1] + 2 * mid - 1) pter2++;
                dp[pter2 - 1][j] = min (dp[pter2 - 1][j], dp[i][j] + 1);
            }
        }
        bool ok = 0;
        for (int j = 0; j <= p; ++j) {
            if (dp[n][j] <= q) { ok = 1; break; }
        }
        if (ok) r = mid;
        else l = mid + 1;
    }

    cout << l;

    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 31832 KB Output is correct
2 Correct 2 ms 31832 KB Output is correct
3 Correct 238 ms 31968 KB Output is correct
4 Correct 2 ms 31968 KB Output is correct
5 Correct 2 ms 31968 KB Output is correct
6 Correct 2 ms 31968 KB Output is correct
7 Correct 222 ms 32084 KB Output is correct
8 Correct 228 ms 32096 KB Output is correct
9 Correct 245 ms 32096 KB Output is correct
10 Correct 224 ms 32096 KB Output is correct
11 Correct 232 ms 32096 KB Output is correct
12 Correct 218 ms 32096 KB Output is correct
13 Correct 210 ms 32096 KB Output is correct
14 Correct 210 ms 32096 KB Output is correct
15 Correct 224 ms 32164 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 32164 KB Output is correct
2 Correct 230 ms 32164 KB Output is correct
3 Correct 414 ms 32176 KB Output is correct
4 Correct 2 ms 32176 KB Output is correct
5 Correct 2 ms 32176 KB Output is correct
6 Correct 2 ms 32176 KB Output is correct
7 Correct 236 ms 32240 KB Output is correct
8 Correct 270 ms 32252 KB Output is correct
9 Correct 322 ms 32252 KB Output is correct
10 Correct 457 ms 32252 KB Output is correct
11 Correct 247 ms 32252 KB Output is correct
12 Correct 405 ms 32252 KB Output is correct
13 Correct 259 ms 32252 KB Output is correct
14 Correct 266 ms 32252 KB Output is correct
15 Correct 225 ms 32252 KB Output is correct