Submission #40349

#TimeUsernameProblemLanguageResultExecution timeMemory
40349krauchWatching (JOI13_watching)C++14
100 / 100
172 ms9192 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair < int, int > PII; #define F first #define S second #define mkp make_pair #define eb emplace_back #define all(a) a.begin(), a.end() #define sz(a) (int)a.size() #define forn(x, a, b) for (int x = a; x <= b; ++x) #define for1(x, a, b) for (int x = a; x >= b; --x) const ll ool = 1e18 + 9; const int N = 3e3 + 3, oo = 1e9 + 9; int n, P, Q, a[N], d[N][N]; bool check(int W) { int ptr = 1; forn(i, 0, P) forn(j, 0, Q) d[i][j] = 1; forn(i, 0, P) { forn(j, 0, Q) { if (d[i][j] == -1) continue; int ptr = d[i][j]; while (ptr <= n && a[ptr] - a[d[i][j]] + 1 <= W) { ++ptr; } d[i + 1][j] = max(d[i + 1][j], ptr); while (ptr <= n && a[ptr] - a[d[i][j]] + 1 <= 2 * W) { ++ptr; } d[i][j + 1] = max(d[i][j + 1], ptr); } } return (d[P][Q] == n + 1); } int main() { #ifdef krauch freopen("input.txt", "r", stdin); #endif cin >> n >> P >> Q; Q = min(Q, n); P = min(P, n - Q); forn(i, 1, n) { cin >> a[i]; } sort(a + 1, a + n + 1); int l = 1, r = a[n]; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l << "\n"; return 0; }

Compilation message (stderr)

watching.cpp: In function 'bool check(int)':
watching.cpp:23:9: warning: unused variable 'ptr' [-Wunused-variable]
     int ptr = 1;
         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...