oj.uz

Submission #109888

# Submission time Handle Problem Language Result Execution time Memory
109888 2019-05-08T10:03:57 Z cgiosy Watching (JOI13_watching) C++17
0 / 100
 174 ms 8412 KB 
#include <cstdio>
#include <algorithm>
#define rep(i,x,n) for(int i=x; i<=n; i++)
inline short min(const short x, const short y) { return x<y ? x : y; }

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

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

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%hd%hd%hd", &n, &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:10:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf("%d", a+i);
               ~~~~~^~~~~~~~~~~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8320 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 174 ms 8412 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Incorrect 21 ms 8320 KB Output isn't correct
6 Halted 0 ms 0 KB -