Submission #1253370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253370		DangerNoodle7591	구경하기 (JOI13_watching)	C++20	50 / 100	177 ms	9500 KiB

watching

#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;

    
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50