Submission #272857

#	Time	Username	Problem	Language	Result	Execution time	Memory
272857		toonewbie	Watching (JOI13_watching)	C++17	100 / 100	192 ms	16504 KiB

watching

#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,x,n) for(int i=x; i<=n; i++)

int a[2048], d[2048][2048], n, x, y;
int main() {
  scanf("%d%d%d", &n, &x, &y);
  if(n<y) y=n; if(n-y<x) x=n-y;
  rep(i, 1, n) scanf("%d", a+i);
  std::sort(a+1, a+n+1);

  int l=1, r=a[n]-a[1]+1;
  while(l<r) {
    int m=(l+r)/2, p=0, q=0;
    rep(i, 0, n) {
      while(p<=i && a[p]<=a[i]-m) p++;
      while(p<=i && a[q]<=a[i]-2*m) q++;
      rep(j, !i, x) d[i][j]=i ? j ? std::min(d[p-1][j-1], d[q-1][j]+1) : d[q-1][j]+1 : 0;
    }
    if(d[n][x]<=y) r=m;
    else l=m+1;
  }
  printf("%d", r);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:9:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |   if(n<y) y=n; if(n-y<x) x=n-y;
      |   ^~
watching.cpp:9:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    9 |   if(n<y) y=n; if(n-y<x) x=n-y;
      |                ^~
watching.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |   scanf("%d%d%d", &n, &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:10:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |   rep(i, 1, n) scanf("%d", a+i);
      |                ~~~~~^~~~~~~~~~~

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