제출 #1253418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253418		DangerNoodle7591	Watching (JOI13_watching)	C++20	100 / 100	788 ms	11940 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 2005
#define pb push_back

vector<int> arr;
int dp[N][N];

int solve(int n,int p,int q,int w){
  dp[0][0]=-1;
  for(int i=0;i<=p;i++){
    for(int j=0;j<=q;j++){
      dp[i][j]=-1;
      if(i){
        int deg=upper_bound(arr.begin(),arr.end(),arr[dp[i-1][j]+1]+w-1 )-arr.begin();
        deg-=1;
        dp[i][j]=max(dp[i][j],deg);
      }
      if(j){
        int deg=upper_bound(arr.begin(),arr.end(),arr[dp[i][j-1]+1]+w*2-1 )-arr.begin();
        deg-=1;
        dp[i][j]=max(dp[i][j],deg);
      }
      //cout<<i<<" "<<j<<": "<<dp[i][j]<<endl;
      if(dp[i][j]>=n-1)return 1;
    }
  }
  return 0;
}

signed main(){
  lalala;
  int n,p,q;cin>>n>>p>>q;
  for(int i=1;i<=n;i++){
    int a;cin>>a;
    arr.pb(a);
  }
  sort(arr.begin(),arr.end());
  int l=1,r=1000000105;
  int cev=-1;
  //l=4;r=4;
  while(l<=r){
    int mid=(l+r)/2;
    //cout<<mid<<endl;
    if(solve(n,p,q,mid)){
      cev=mid;
      r=mid-1;
    }
    else l=mid+1;
  }
  cout<<cev<<endl;

    
}

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