Submission #966394

#TimeUsernameProblemLanguageResultExecution timeMemory
966394oviyan_gandhiWatching (JOI13_watching)C++14
0 / 100
8 ms2648 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; i < n; i++){ nw[i] = lower_bound(a+i, a+n+1, a[i] + w) - a - 1; nw2[i] = lower_bound(a+i, a+n+1, a[i] + 2*w) - a - 1; } nw[0] = nw[1]; nw2[0] = nw2[1]; 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...