Submission #107754

#	Time	Username	Problem	Language	Result	Execution time	Memory
107754		tieunhi	Watching (JOI13_watching)	C++14	100 / 100	339 ms	16248 KiB

watching

#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define ll long long
#define N 2005
#define maxc 1000000007

using namespace std;

int dp[N][N];
int n, P, Q;
vector<int> a;
bool check(int len) {
    memset(dp, 60, sizeof dp);
    dp[0][0] = 0;
    FOR(i, 1, n)
    {
        int x1 = a[i] - len + 1;
        int pos1 = lower_bound(a.begin(), a.end(), x1) - a.begin() - 1;

        int x2 = a[i] - 2*len + 1;
        int pos2 = lower_bound(a.begin(), a.end(), x2) - a.begin() - 1;


        FOR(j, 0, P) {
            if (j) dp[i][j] = min(dp[i][j], dp[pos1][j-1]);
            dp[i][j] = min(dp[i][j], dp[pos2][j] + 1);
        }
    }
    FOR(j, 0, P)
        if (dp[n][j] <= Q) return 1;
    return 0;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> P >> Q;
    if (P + Q >= n) {
        cout <<1;
        return 0;
    }


    FOR(i, 1, n) {
        int x; cin >> x;
        a.PB(x);
    }
    a.PB(-2*maxc);

    sort(a.begin(), a.end());
    int L = 0, R = maxc;
    while (R - L > 1) {
        int mid = (R + L)/2;
        if (check(mid)) R = mid;
        else L = mid;
    }
    cout <<R;
}

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