이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// define ctdl
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
// define files
#define TASKS "EVENTS."
#define fast ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define endl '\n'
#define all(x) x.begin(),x.end()
#define FORU(i,a,b) for(int i = a, _b = b; i <= _b ; i++)
#define FORD(i,a,b) for(int i = a, _b = b; i >= _b ; i--)
using namespace std;
const int maxsub1 = 200, maxn = 2000,oo = 1e9 ;
int n, numP, numQ ;
int a[maxn+1] ;
void getMin(int &x, int y)
{
x = min(x,y) ;
}
namespace sub1
{
int dp[maxn+1][maxn+1];
bool check(int num)
{
memset(dp,0x3f,sizeof(dp)) ;
dp[0][0] = 0 ;
FORU(i,0,n) FORU(j,0,numP) if(dp[i][j] <= numQ)
{
int L = i + 1, R = i + 1 ;
while(R <= n && a[L] + num-1 >= a[R] && j < numP)
{
getMin(dp[R][j+1],dp[i][j]) ;
R++ ;
}
R = i + 1 ;
while(R <= n && a[L] + num*2-1 >= a[R])
{
getMin(dp[R][j],dp[i][j] + 1) ;
R++ ;
}
}
FORU(j,0,numP) if(dp[n][j] <= numQ)
{
return true ;
}
return false ;
}
void solve()
{
int L = 1, R = 1e9,ans =0 ;
while(L <= R)
{
int mid = (L+R)>>1 ;
if(check(mid)) R = mid - 1,ans=mid;
else L = mid + 1 ;
}
cout << ans ;
}
}
namespace lastsub
{
int dp[maxn+1][maxn+1] ;
int p[maxn+1], q[maxn+1] ;
bool check(int num)
{
memset(dp,0x3f,sizeof(dp)) ;
dp[0][0] = 0 ;
int tmp = 1 ;
FORU(i,1,n)
{
while(tmp < n && a[i] + num - 1 >= a[tmp+1]) tmp++ ;
p[i] = tmp ;
}
tmp = 1 ;
FORU(i,1,n)
{
while(tmp < n && a[i] + num*2 - 1 >= a[tmp+1]) tmp++ ;
q[i] = tmp ;
}
FORU(i,0,n) FORU(j,0,n) if(dp[i][j] <= numQ)
{
int R = p[i+1] ;
getMin(dp[R][j+1],dp[i][j]) ;
R = q[i+1] ;
getMin(dp[R][j],dp[i][j] + 1) ;
}
FORU(j,0,numP) if(dp[n][j] <= numQ) return true ;
return false ;
}
void solve()
{
int L = 1, R = 1e9,ans =0 ;
while(L <= R)
{
int mid = (L+R)>>1 ;
if(check(mid)) R = mid - 1,ans=mid;
else L = mid + 1 ;
}
cout << ans ;
}
}
int main()
{
fast ;
//freopen(TASKS"INP","r",stdin) ;
//freopen(TASKS"OUT","w",stdout) ;
cin >> n >> numP >> numQ ;
FORU(i,1,n) cin >> a[i] ;
sort(&a[1],&a[n+1]) ;
if(n <= numP + numQ)
{
cout << 1 ;
return 0 ;
}
if(n <= 100) sub1::solve() ;
else lastsub::solve() ;
return 0 ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |