Submission #37829

#	Time	Username	Problem	Language	Result	Execution time	Memory
37829		nickyrio	Watching (JOI13_watching)	C++14	0 / 100	6 ms	18120 KiB

watching

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 2020
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;

int n, p, q, dp[N][N], a[N];
//dp[i][j] : Minimun the large camera used when fill from 1..i, used j small camera

bool ok(int w) {
    FOR(i, 0, n) FOR(j, 0, p) dp[i][j] = 1e9;
    dp[0][0] = 0;
    FOR(i, 1, n) {
        int psmall = upper_bound(a + 1, a + n + 1, a[i] - w + 1) - a - 1;
        int plarge = upper_bound(a + 1, a + n + 1, a[i] - w - w + 1) - a - 1;
        dp[i][0] = dp[plarge][0] + 1;
        FOR(j, 1, p) {
            dp[i][j] = min(dp[psmall][j - 1], dp[plarge][j] + 1);
        }
    }
    FOR(j, 0, p) if(dp[n][j] <= q) return true;
    return false;
}

int main() {
    IO; ios :: sync_with_stdio(false);
    cin >> n >> p >> q;
    p = min(p, n);
    FOR(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 0, r = 1e9, cur = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (ok(m)) {
            cur = m;
            r = m - 1;
        } else l = m + 1;
    }
    cout << cur;
}

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