제출 #1253370

#제출 시각아이디문제언어결과실행 시간메모리
1253370DangerNoodle7591구경하기 (JOI13_watching)C++20
50 / 100
177 ms9500 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 105

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;i<=n;i++){
      if(arr[i]-arr[x]+1<=w){
        dp[x][p][q]=max(dp[x][p][q],solve(i+1,p-1,q,w));
      }
      else break;
    }
  }
  if(q){
    for(int i=x;i<=n;i++){
      if(arr[i]-arr[x]+1<=w*2){
        dp[x][p][q]=max(dp[x][p][q],solve(i+1,p,q-1,w));
      }
      else break;
    }
  }
  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=1000000105;
  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...