Submission #499171

#	Time	Username	Problem	Language	Result	Execution time	Memory
499171		khoabright	Watching (JOI13_watching)	C++17	50 / 100	178 ms	16084 KiB

watching

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()

int n, P, Q;
vector<int> a;
const int N = 2005;
const int inf = 1e9;
int L[N][2];
int dp[N][N];

bool check(int w) {
    rep(i, 0, n + 2) rep(j, 0, n + 2) {
        dp[i][j] = inf;
    }

    rep(i, 1, n) {
        L[i][0] = lower_bound(all1(a), a[i] - w + 1) - a.begin();
        L[i][1] = lower_bound(all1(a), a[i] - 2 * w + 1) - a.begin();
    }

//    rep(i, 1, n) {
//        cout << L[i][0] << ' ' << L[i][1] << '\n';
//    }

    rep(i, 0, P) dp[0][i] = 0;

    rep(i, 1, n) rep(p, 1, P) {
        dp[i][p] = min(dp[L[i][0] - 1][p - 1], dp[L[i][1] - 1][p] + 1);
        //cout<<"i,p,dp="<<i<<' '<<p<<' '<<dp[i][p]<<'\n';
        //if (dp[i][p] <= Q) return 1;
    }

    return dp[n][P] <= Q;
}

void solve() {
    cin >> n >> P >> Q;
    P = min(P, n);
    Q = min(Q, n);
    a.resize(n + 1);
    rep(i, 1, n) cin >> a[i];
    sort(all1(a));

   // cout << check(3) << '\n';
    int l = 1, r = inf, ans = 0;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            ans = m, r = m - 1;
        }
        else l = m + 1;
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    solve();
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50