제출 #444938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444938		ivan_tudor	구경하기 (JOI13_watching)	C++14	100 / 100	258 ms	16068 KiB

watching

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int v[N];
int dp[N][N];
int n, p, q;
bool check(int w){
  int lst, lst2;
  for(int i =0 ; i<N; i++){
    for(int j = 0; j < N; j++){
      dp[i][j] = INT_MAX;
      dp[0][j] = 0;
    }
  }
  lst = lst2 = 0;
  for(int i =1 ; i<=n; i++){
    while(lst < i && v[i] - v[lst + 1] + 1 > w)
      lst++;
    while(lst2 < i && v[i] - v[lst2 + 1] + 1 > 2*w)
      lst2++;
    for(int j = 0; j <= i; j++ ){
      if(dp[lst][j] != INT_MAX)
        dp[i][j] = min(dp[i][j], dp[lst][j] + 1);
      if(j)
        dp[i][j] = min(dp[i][j], dp[lst2][j-1]);
    }
  }
  for(int i = 0; i <=q; i++){
    if(dp[n][i] <=p)
      return true;
  }
  return false;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>p>>q;
  for(int i =1 ; i<=n; i++){
    cin>>v[i];
  }
  sort(v+1, v+n+1);
  if(p + q >= n){
    cout<<"1";
    return 0;
  }
  int pas = 0;
  for(int p2 = 1<<29; p2>0; p2>>=1){
    if(check(pas + p2) == false)
      pas+=p2;
  }
  cout<<pas + 1;
  return 0;
}

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