#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,avx")
#pragma GCC optimize("unroll-loops")
int n,m,k;
int dizi[1005];
int dp[2005][2005];
int dps(int x,int y,int z)
{
if(x>n)
return 0;
if(y>m)
return 999999999;
if(dp[x][y]!=-1)
return dp[x][y];
int a=upper_bound(dizi+1,dizi+n+1,dizi[x]+z-1)-dizi;
int b=upper_bound(dizi+1,dizi+n+1,dizi[x]+2*z-1)-dizi;
int kucuk=dps(a,y+1,z);
int buyuk=dps(b,y,z)+1;
return dp[x][y]=min(kucuk,buyuk);
}
int f(int x)
{
memset(dp,-1,sizeof dp);
dp[n][n]=0;
dps(1,0,x);
for(int j=0;j<=m;j++)
{
if(dp[n][j]<=k)
return 1;
}
return 0;
}
void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>dizi[i];
sort(dizi+1,dizi+1+n);
int bas=0;
int son=1e9;
while(bas<son)
{
int orta=(bas+son)/2;
if(f(orta)==1)
son=orta;
else bas=orta+1;
}
cout<<bas<<endl;
}
signed main()
{
fast1
//freopen ("lca.gir","r",stdin);
//freopen ("lca.cik","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
202 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
408 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |