oj.uz

Submission #34543

# Submission time Handle Problem Language Result Execution time Memory
34543 2017-11-12T08:20:17 Z cheater2k Watching (JOI13_watching) C++14
100 / 100
 66 ms 17748 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;

int n, p, q;
long long a[N];
int to1[N], to2[N];
int f[N][N];

bool check(int w) {
	int pt = 1;
	for (int i = 1; i <= n; ++i) {
		while(pt <= n && a[i] + w - 1 >= a[pt]) ++pt; --pt;
		to1[i] = pt;
	}
	pt = 1;
	for (int i = 1; i <= n; ++i) {
		while(pt <= n && a[i] + 2LL * w - 1 >= a[pt]) ++pt; --pt;
		to2[i] = pt;
	}

	for (int i = 0; i <= p; ++i) {
		for (int j = 0; j <= q; ++j) {
			f[i][j] = 0;
			if (i > 0) f[i][j] = max(f[i][j], to1[f[i-1][j] + 1]);
			if (j > 0) f[i][j] = max(f[i][j], to2[f[i][j-1] + 1]);

			if (f[i][j] >= n) return true;
		}
	}

	return false;
}

int main() {
	scanf("%d %d %d", &n, &p, &q);
	if (p >= n || q >= n) {
		return printf("1\n"), 0;
	}
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	
	int l = 1, r = 1e9;
	while(l < r) {
		int mid = ((l + r) >> 1);
		if (check(mid)) r = mid; else l = mid + 1;
	}
	printf("%d\n", l);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:41:48: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                ^
watching.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &p, &q);
                               ^
watching.cpp:41:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                 ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17748 KB Output is correct
2 Correct 0 ms 17748 KB Output is correct
3 Correct 0 ms 17748 KB Output is correct
4 Correct 0 ms 17748 KB Output is correct
5 Correct 0 ms 17748 KB Output is correct
6 Correct 0 ms 17748 KB Output is correct
7 Correct 0 ms 17748 KB Output is correct
8 Correct 0 ms 17748 KB Output is correct
9 Correct 0 ms 17748 KB Output is correct
10 Correct 0 ms 17748 KB Output is correct
11 Correct 0 ms 17748 KB Output is correct
12 Correct 0 ms 17748 KB Output is correct
13 Correct 0 ms 17748 KB Output is correct
14 Correct 0 ms 17748 KB Output is correct
15 Correct 0 ms 17748 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17748 KB Output is correct
2 Correct 0 ms 17748 KB Output is correct
3 Correct 33 ms 17748 KB Output is correct
4 Correct 0 ms 17748 KB Output is correct
5 Correct 0 ms 17748 KB Output is correct
6 Correct 0 ms 17748 KB Output is correct
7 Correct 0 ms 17748 KB Output is correct
8 Correct 9 ms 17748 KB Output is correct
9 Correct 13 ms 17748 KB Output is correct
10 Correct 19 ms 17748 KB Output is correct
11 Correct 6 ms 17748 KB Output is correct
12 Correct 66 ms 17748 KB Output is correct
13 Correct 0 ms 17748 KB Output is correct
14 Correct 0 ms 17748 KB Output is correct
15 Correct 0 ms 17748 KB Output is correct