제출 #911182

#제출 시각아이디문제언어결과실행 시간메모리
911182Acanikolic구경하기 (JOI13_watching)C++14
0 / 100
1094 ms262144 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define F first #define S second using namespace std; const int N = 2000 + 10; const int mod = 1e9 + 7; const int inf = 1e18; int n,p,q,a[N]; bool check(int x) { vector<vector<int>>dp(n + 1,vector<int>(p + 2,inf)); for(int i = 0; i <= p; i++) dp[0][i] = 0; int ans1 = 1,ans2 = 1; for(int i = 1; i <= n; i++) { for(int j = 0; j <= p; j++) { if(j > 0) dp[i][j] = min(dp[i][j],dp[i - 1][j - 1]); dp[i][j] = min(dp[i][j],dp[i - 1][j] + 1); while(ans1 + 1 <= n && a[i] + x - 1 >= a[ans1 + 1]) ans1 += 1; dp[ans1][j + 1] = min(dp[ans1][j + 1],dp[i - 1][j]); while(ans2 + 1 <= n && a[i] + 2 * x - 1 >= a[ans2 + 1]) ans2 += 1; dp[ans2][j] = min(dp[ans2][j],dp[i - 1][j] + 1); } } if(dp[n][p] <= q) return true; return false; /*for(int i = 1; i <= n; i++) { for(int j = 0; j <= p; j++) cout << dp[i][j] << " "; cout << endl; }*/ } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> p >> q; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1,a + n + 1); int l = 1,r = 1e9,ans = -1; while(l <= r) { int mid = (l + r) / 2; if(check(mid)) { ans = mid; r = mid - 1; }else { l = mid + 1; } } cout << ans; //cout << check(9); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...