Submission #1076017

#TimeUsernameProblemLanguageResultExecution timeMemory
1076017andrewpWatching (JOI13_watching)C++14
100 / 100
186 ms16228 KiB
//Dedicated to my love, ivaziva #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using ll = int64_t; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define dbg(x) cerr << #x << ": " << x << '\n'; constexpr int N = 2e3 + 5, W = (int)1e9 + 10; int n, p, q, a[N], dp[N][N]; bool check(int w) { for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = W; } } dp[0][0] = 0; int f = 0, s = 0; for (int i = 1; i <= n; i++) { while (a[i] >= a[f + 1] + w) { f++; } while (a[i] >= a[s + 1] + 2 * w) { s++; } for (int j = 0; j <= n; j++) { dp[i][j] = dp[f][j] + 1; if (j) { dp[i][j] = min(dp[i][j], dp[s][j - 1]); } } } for (int i = 0; i <= min(n, q); i++) { if (dp[n][i] <= p) { return true; } } return false; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); cin >> n >> p >> q; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); int l = 1, r = W, ans = W; while (l <= r) { int mid = l + r >> 1; if (check(mid)) { r = mid - 1; ans = mid; } else { l = mid + 1; } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

watching.cpp: In function 'int32_t main()':
watching.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...