Submission #958870

#TimeUsernameProblemLanguageResultExecution timeMemory
958870PringWatching (JOI13_watching)C++17
0 / 100
12 ms31324 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define int long long #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) typedef pair<int, int> pii; const int MXN = 2005, MXC = 1000000005; int n, X, Y, a[MXN]; int dp[MXN][MXN], l[MXN], l2[MXN]; void PRE(int w) { int p = 0, pp = 0; FOR(i, 1, n + 1) { while (a[i] - a[p] >= w) p++; while (a[i] - a[pp] >= 2 * w) pp++; l[i] = p - 1; l2[i] = pp - 1; } } bool check(int w) { PRE(w); dp[0][0] = 0; FOR(i, 1, n + 1) dp[0][i] = dp[0][l2[i]] + 1; deque<pii> dq, dq2; auto POP = [&](deque<pii> &dq, int t) -> void { while (dq.size() && dq.front().fs < t) dq.pop_front(); }; auto PUSH = [&](deque<pii> &dq, int id, int val) -> void { while (dq.size() && dq.back().sc >= val) dq.pop_back(); dq.push_back(mp(id, val)); }; FOR(j, 1, X + 1) { dp[j][0] = 0; dq.clear(); dq2.clear(); PUSH(dq, 0, dp[j - 1][0]); PUSH(dq2, 0, dp[j][0]); FOR(i, 1, n + 1) { POP(dq, l[i]); POP(dq2, l2[i]); dp[i][j] = min(dq.front().sc, dq2.front().sc + 1); PUSH(dq, i, dp[j - 1][i]); PUSH(dq2, i, dp[j][i]); } } // FOR(i, 0, n + 1) { // FOR(j, 0, X + 1) cout << dp[i][j] << ' '; // cout << endl; // } FOR(j, 0, X + 1) if (dp[j][n] <= Y) return true; return false; // FOR(i, 0, n + 1) cout << dp[i][0] << '\n'; // return true; } void miku() { cin >> n >> X >> Y; FOR(i, 1, n + 1) cin >> a[i]; sort(a + 1, a + n + 1); if (X + Y >= n) { cout << 1 << '\n'; return; } a[0] = -2 * MXC; // check(4); // return; int l = 0, r = MXC; while (l + 1 < r) { int mid = (l + r) >> 1; (check(mid) ? r : l) = mid; } cout << r << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...