Submission #539161

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
539161	2022-03-18 14:04:30	astoria	Watching (JOI13_watching)	C++14	100 / 100	233 ms	15988 KiB

watching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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