Submission #539161

#	Time	Username	Problem	Language	Result	Execution time	Memory
539161		astoria	Watching (JOI13_watching)	C++14	100 / 100	233 ms	15988 KiB

watching

#include <bits/stdc++.h>
using namespace std;

int N,P,Q;
int events[2001], prep[2001], preq[2001], minq[2001][2001];

bool f (int w){
  for (int i=N-1; i>=0; i--){
    prep[i] = int(lower_bound(events, events+N, events[i]+w)-events);
    preq[i] = int(lower_bound(events, events+N, events[i]+min(1000000001, 2*w))-events);
    for (int p=0; p<=P; p++){
      /*if (q==0) minp[i][q] = minp[prep[i]-1][q]+1;
      else minp[i][q] = min(minp[prep[i]-1][q]+1 , minp[preq[i]-1][q-1]);*/
      minq[i][p] = 1000000001;
      if (p>0) minq[i][p] = minq[prep[i]][p-1];
      minq[i][p] = min( minq[i][p], minq[preq[i]][p]+1 );
    }
  }
  if (minq[0][P]<=Q) return true;
  else return false;
}

int binarySearch(){
  int L=0; int R=1000000001;
  while (L<R){
    int middle = (L+R)/2;
    if (f(middle)){
      R = middle;
    }
    else{
      L = middle+1;
    }
  }
  return L;
}

int main(){
  cin >> N >> P >> Q;
  for (int i=0; i<N; i++){
    cin >> events[i];
  }
  if ((P+Q)>=N){
      cout << 1;
      return 0;
  }
  sort(events,events+N);
  cout << binarySearch();
}

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