Submission #471006

#TimeUsernameProblemLanguageResultExecution timeMemory
471006iulia13Watching (JOI13_watching)C++14
100 / 100
287 ms16012 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e3 + 5; int n, p, q; int a[N]; int dp[N][N]; int check(int val) { int i1 = 0, i2 = 0, i, j; for (i = 0; i <= n; i++) for (j = 0; j <= p; j++) dp[i][j] = q + 1; dp[0][0] = 0; for (i = 1; i <= n; i++) { while (a[i1 + 1] + val <= a[i]) i1++; while (a[i2 + 1] + val * 2 <= a[i]) i2++; for (j = 0; j <= p; j++) { if (j) dp[i][j] = min(dp[i][j], dp[i1][j - 1]); dp[i][j] = min(dp[i][j], dp[i2][j] + 1); } } for (i = 0; i <= p; i++) if (dp[n][i] <= q) return 1; return 0; } int main() { int i, sol; cin >> n >> p >> q; p = min(p, n); q = min(q, n); for (i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int st = 1, dr = 1e9; while (st <= dr) { int mid = (st + dr) / 2; if (check(mid)) { sol = mid; dr = mid - 1; } else st = mid + 1; } cout << sol; return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:54:13: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     cout << sol;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...