#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
/// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
#define OPT ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define arr array
#define vll vector<int>
#define int long long
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
#define fi first
#define se second
#define rep(i,j,k) for(int i = j; i <= k; ++i)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define endll '\n'
using namespace std;
const int N = 2e3 + 3;
const int INF = 1e18;
int a[N];
int dp[N][N];
int n, p, q;
bool check(int w)
{
for(int i = 0; i <= p; ++i)
{
int idx1 = 0, idx2 = 0;
for(int j = 1; j <= n; ++j)
{
dp[i][j] = INF;
while(idx1 < n && a[idx1 + 1] <= a[j] - w)
{
idx1++;
}
while(idx2 < n && a[idx2 + 1] <= a[j] - w * 2)
{
idx2++;
}
dp[i][j] = dp[i][idx2] + 1;
if(i > 0)
{
dp[i][j] = min(dp[i][j], dp[i - 1][idx1]);
}
}
}
return dp[p][n];
}
signed main()
{
cin >> n >> p >> q;
for(int i = 1; i <= n; ++i)
cin >> a[i];
if(p + q >= n)
{
cout << 1;
return 0;
}
sort(a + 1, a + n + 1);
int lb = 1, rb = 1e9, ans, mid;
while(lb < rb)
{
mid = (lb + rb) >> 1;
if(check(mid) > q)
{
lb = mid + 1;
ans = mid;
}
else
{
rb = mid;
}
}
cout << lb;
}
Compilation message
watching.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization("unroll-loops")
|
watching.cpp: In function 'int main()':
watching.cpp:65:27: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
65 | int lb = 1, rb = 1e9, ans, mid;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
