oj.uz

Submission #109889

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

int a[2048], n, x, y; short d[2048][2048];
int main() {
	scanf("%d%d%d", &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;
		memset(d[1], 0x3f, 2047*2048*2);
		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:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:11: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 28 ms 8576 KB Output is correct
2 Correct 23 ms 8576 KB Output is correct
3 Incorrect 22 ms 8448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8576 KB Output is correct
2 Correct 25 ms 8576 KB Output is correct
3 Correct 222 ms 8576 KB Output is correct
4 Correct 315 ms 8588 KB Output is correct
5 Correct 44 ms 8576 KB Output is correct
6 Correct 287 ms 8548 KB Output is correct
7 Correct 34 ms 8580 KB Output is correct
8 Correct 55 ms 8580 KB Output is correct
9 Correct 148 ms 8696 KB Output is correct
10 Correct 292 ms 8696 KB Output is correct
11 Correct 45 ms 8576 KB Output is correct
12 Incorrect 174 ms 8576 KB Output isn't correct
13 Halted 0 ms 0 KB -