oj.uz

Submission #164555

# Submission time Handle Problem Language Result Execution time Memory
164555 2019-11-21T12:48:04 Z TAISA_ Watching (JOI13_watching) C++14
100 / 100
 280 ms 16280 KB 
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int n, p, q;
vector<ll> a;
int dp[2010][2010];
bool check(int w) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int k1 = lower_bound(all(a), a[i] - w + 1LL) - a.begin();
        int k2 = lower_bound(all(a), a[i] - 2LL * w + 1LL) - a.begin();
        --k1;
        --k2;
        for (int j = 0; j <= i; j++) {
            if (j > 0) {
                chmin(dp[i][j], dp[k1][j - 1]);
            }
            chmin(dp[i][j], dp[k2][j] + 1);
        }
    }
    for (int i = 0; i <= n; i++) {
        if (i <= p && dp[n][i] <= q) {
            return true;
        }
    }
    return false;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> p >> q;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    a.push_back(-LINF);
    sort(all(a));
    int ok = INF, ng = 0;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2LL;
        if (check(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    cout << ok << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 7 ms 380 KB Output is correct
4 Correct 3 ms 764 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 760 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 3 ms 764 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 16188 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 199 ms 16120 KB Output is correct
4 Correct 280 ms 16120 KB Output is correct
5 Correct 201 ms 16176 KB Output is correct
6 Correct 197 ms 16216 KB Output is correct
7 Correct 205 ms 16120 KB Output is correct
8 Correct 206 ms 16100 KB Output is correct
9 Correct 208 ms 16236 KB Output is correct
10 Correct 231 ms 16164 KB Output is correct
11 Correct 205 ms 16176 KB Output is correct
12 Correct 209 ms 16184 KB Output is correct
13 Correct 206 ms 16120 KB Output is correct
14 Correct 220 ms 16280 KB Output is correct
15 Correct 204 ms 16120 KB Output is correct