Submission #966399

#TimeUsernameProblemLanguageResultExecution timeMemory
966399oviyan_gandhiWatching (JOI13_watching)C++14
100 / 100
52 ms31312 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #define N 2001 int n, p, q, a[N], dp[N][N], nw[N], nw2[N]; // next w, next 2w bool check(int w){ for (int i = 1, j = 1, k = 1; i <= n; i++){ while (j < n && a[j+1] - a[i] < w) j++; while (k < n && a[k+1] - a[i] < 2*w) k++; nw[i] = j; nw2[i] = k; } for (int i = 0; i <= p; i++){ for (int j = 0; j <= q; j++){ dp[i][j] = 0; if (i) dp[i][j] = max(dp[i][j], nw[dp[i-1][j]+1]); if (j) dp[i][j] = max(dp[i][j], nw2[dp[i][j-1]+1]); if (dp[i][j] == n) return true; } } return false; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> p >> q; for (int i = 1; i <= n; i++) cin >> a[i]; if ((p + q) >= n){ cout << "1\n"; return 0; } sort(a+1, a+n+1); int l = 0, r = 1e9, ans = r; while (l <= r){ int mid = (l+r)/2; if (check(mid)) ans = mid, r = mid-1; else l = mid+1; } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...