oj.uz

Submission #531877

# Submission time Handle Problem Language Result Execution time Memory
531877 2022-03-01T19:05:38 Z rainboy Watching (JOI13_watching) C
100 / 100
 264 ms 15956 KB 
#include <stdio.h>

#define N	2000

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

void sort(int *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

int main() {
	static int xx[N], dp[N + 1][N + 1];
	int n, k_, l_, i, j1, j2, k, lower, upper;

	scanf("%d%d%d", &n, &k_, &l_), k_ = min(k_, n), l_ = min(l_, n);
	for (i = 0; i < n; i++)
		scanf("%d", &xx[i]);
	sort(xx, 0, n);
	lower = 0, upper = 0x3f3f3f3f;
	while (upper - lower > 1) {
		int w = (lower + upper) / 2, ok;

		for (i = 0; i <= n; i++)
			for (k = 0; k <= k_; k++)
				dp[i][k] = l_ + 1;
		dp[0][0] = 0;
		for (i = 0, j1 = 0, j2 = 0; i <= n; i++) {
			while (j1 < n && xx[j1] - xx[i] < w)
				j1++;
			while (j2 < n && xx[j2] - xx[i] < w * 2)
				j2++;
			for (k = 0; k <= k_; k++) {
				if (k < k_)
					dp[j1][k + 1] = min(dp[j1][k + 1], dp[i][k]);
				if (dp[i][k] < l_)
					dp[j2][k] = min(dp[j2][k], dp[i][k] + 1);
			}
		}
		ok = 0;
		for (k = 0; k <= k_; k++)
			if (dp[n][k] <= l_) {
				ok = 1;
				break;
			}
		if (ok)
			upper = w;
		else
			lower = w;
	}
	printf("%d\n", upper);
	return 0;
}

Compilation message

watching.c: In function 'main':
watching.c:36:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d%d%d", &n, &k_, &l_), k_ = min(k_, n), l_ = min(l_, n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.c:38:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 580 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 2 ms 736 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 660 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 656 KB Output is correct
12 Correct 2 ms 664 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 664 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8228 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 209 ms 15948 KB Output is correct
4 Correct 261 ms 15948 KB Output is correct
5 Correct 20 ms 8924 KB Output is correct
6 Correct 264 ms 15956 KB Output is correct
7 Correct 9 ms 8396 KB Output is correct
8 Correct 25 ms 9300 KB Output is correct
9 Correct 103 ms 14200 KB Output is correct
10 Correct 222 ms 15956 KB Output is correct
11 Correct 21 ms 8908 KB Output is correct
12 Correct 241 ms 15952 KB Output is correct
13 Correct 11 ms 8368 KB Output is correct
14 Correct 9 ms 8368 KB Output is correct
15 Correct 8 ms 8396 KB Output is correct