이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
vector<int>a;
bool check(int n,int p,int q,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++) {
while(ans1 + 1 <= n && a[i] + x - 1 >= a[ans1 + 1]) ans1 += 1;
while(ans2 + 1 <= n && a[i] + 2 * x - 1 >= a[ans2 + 1]) ans2 += 1;
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);
dp[ans1][j + 1] = min(dp[ans1][j + 1],dp[i - 1][j]);
dp[ans2][j] = min(dp[ans2][j],dp[i - 1][j] + 1);
}
}
if(dp[n][p] <= q) return true;
return false;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,p,q;
cin >> n >> p >> q;
a.resize(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1,a.end());
int l = 1,r = 1e9,ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(check(n,p,q,mid)) {
ans = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
cout << ans;
//cout << check(9);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |