제출 #835332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835332		epicci23	구경하기 (JOI13_watching)	C++17	100 / 100	334 ms	31676 KiB

watching

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())

inline int in()
{
  int x;cin >> x;
  return x;
}


void solve()
{
  int n=in(),p=in(),q=in();
  
  int ar[n+1];
  for(int i=1;i<=n;i++) ar[i]=in();

  sort(ar+1,ar+n+1);

  if(p+q>=n)
  {
    cout << 1 << endl;
    return;
  }

  int dp[n+1][n+1];

  int l=1,r=(int)1e10;

  while(l<r)
  {
    int m=(l+r)/2;
    bool ok=0;
    for(int i=0;i<=n;i++)
     for(int j=0;j<=n;j++)
      dp[i][j]=3000;

    dp[0][0]=0;

    for(int i=1;i<=n;i++)
    {
      // use p
      int jl=1,jr=i;
      while(jl<jr)
      {
        int jm=(jl+jr)/2;
        if(ar[i]-ar[jm]+1<=m) jr=jm;
        else jl=jm+1;
      }
      
      for(int j=0;j<n;j++)
      {
        if(dp[jl-1][j]!=3000) 
          dp[i][j+1]=min(dp[i][j+1],dp[jl-1][j]);
      }

      // use q
      jl=1,jr=i;
      while(jl<jr)
      {
        int jm=(jl+jr)/2;
        if(ar[i]-ar[jm]+1<=2*m) jr=jm;
        else jl=jm+1;
      }

      for(int j=0;j<=n;j++)
      {
        if(dp[jl-1][j]!=3000) 
          dp[i][j]=min(dp[i][j],dp[jl-1][j]+1);
      }
    }

    for(int j=0;j<=p;j++) if(dp[n][j]<=q) {ok=1;break;}
    
    if(ok) r=m;
    else l=m+1;
  }
  
  cout << l << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//t=in();
  while(t--) solve();

  return 0;
}

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