제출 #1253361

#제출 시각아이디문제언어결과실행 시간메모리
1253361DangerNoodle7591구경하기 (JOI13_watching)C++20
0 / 100
8 ms4420 KiB
#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define int long long int
#define endl '\n'
#define N 102

int arr[N];
int dp[N][N][N];
int n;
int solve(int x,int p,int q,int w){
  if(x>n)return 0;
  if(dp[x][p][q]!=-1)return dp[x][p][q];
  dp[x][p][q]=-2;
  if(p){
    for(int i=x+1;i<=n;i++){
      if(arr[i]-arr[x]+1>w){
        dp[x][p][q]=solve(i,p-1,q,w);
        break;
      }
      if(i==n)dp[x][p][q]=0;
    }
  }
  if(q&&dp[x][p][q]!=0){
    for(int i=x+1;i<=n;i++){
      if(arr[i]-arr[x]+1>w*2){
        dp[x][p][q]=solve(i,p,q-1,w);
        break;
      }
      if(i==n)dp[x][p][q]=0;
    }
  }
  //cout<<x<<" "<<p<<" "<<q<<" "<<dp[x][p][q]<<endl;
  return dp[x][p][q];
}

signed main(){
  lalala;
  int p,q;cin>>n>>p>>q;
  p=min(n,p);
  q=min(n,q);
  arr[0]=-3;
  for(int i=1;i<=n;i++)cin>>arr[i];
  sort(arr,arr+n+1);
  int l=1,r=1000000005;
  int cev=-1;
  while(l<=r){
    int mid=(l+r)/2;
    memset(dp,-1,sizeof(dp));
    if(solve(1,p,q,mid)==0){
      cev=mid;
      r=mid-1;
    }
    else l=mid+1;
  }
  cout<<cev<<endl;

    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...