Submission #164555

#	Time	Username	Problem	Language	Result	Execution time	Memory
164555		TAISA_	Watching (JOI13_watching)	C++14	100 / 100	280 ms	16280 KiB

watching

#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 / 50
• Subtask 2: 50 / 50