Submission #1261868

#TimeUsernameProblemLanguageResultExecution timeMemory
1261868reginoxWatching (JOI13_watching)C++20
0 / 100
24 ms15944 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define all(v) begin(v), end(v) #define pi pair<int, int> #define vi vector<int> using namespace std; const int N = 2e3+3; int n, p, q, a[N]; int dp[N][N]; bool ck(int d){ memset(dp, 0, sizeof(dp)); dp[1][0] = lower_bound(a+1, a+n+1, a[1] + d) - a - 1; dp[0][1] = lower_bound(a+1, a+n+1, a[1] + 2*d) - a - 1; // cout << d << "\n"; for(int i = 1; i <= p; i++){ for(int j = 1; j <= q; j++){ int ff = lower_bound(a+1, a+n+1, a[dp[i-1][j] + 1] + d) - a - 1; dp[i][j] = max(dp[i][j], ff); ff = lower_bound(a+1, a+n+1, a[dp[i][j-1] + 1] + 2*d) - a - 1; dp[i][j] = max(dp[i][j], ff); // cout << dp[i][j] << " "; } // cout << '\n'; } return dp[p][q] >= n; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> p >> q; if(p + q >= n){ cout << 1; return 0; } p = min(p, n), q = min(q, n); for(int i = 1; i <= n; i++) cin >> a[i]; a[n+1] = a[n]; sort(a+1, a+n+1); int ans, L = 1, R = 1e9, mid; while(L <= R){ mid = (L+R)/2; if(ck(mid)){ ans = mid; R = mid - 1; } else L = mid + 1; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...