oj.uz

Submission #39371

# Submission time Handle Problem Language Result Execution time Memory
39371 2018-01-13T06:34:04 Z 14kg Watching (JOI13_watching) C++11
0 / 100
 0 ms 952 KB 
#include <stdio.h>
#include <algorithm>
#define INF 2000000000
#define min2(x,y) (x<y?x:y)

using namespace std;
int n, X, Y, in[2001];
int dp[2001][100001];

bool Can(int len) {
	int *w1, *w2, t1, t2;

	for (int i = 1; i <= n; i++) dp[i][0] = INF;
	for (int i = 1; i <= n; i++) {
		w1 = lower_bound(in + 1, in + n + 1, in[i] - len + 1);
		w2 = lower_bound(in + 1, in + n + 1, in[i] - len * 2 + 1);
		t1 = w1 - in - 1, t2 = w2 - in - 1;

		for (int j = 1; j <= X; j++) {
			dp[i][j] = min2(dp[t1][j - 1], dp[t2][j] + 1);
		}
	}
	return dp[n][X] <= Y;
}
int main() {
	int l = 1, r = 1000000000, mid;

	scanf("%d %d %d", &n, &X, &Y);
	for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
	sort(in + 1, in + n + 1);

	while (l <= r) {
		mid = (l + r) / 2;
		if (Can(mid)) r = mid - 1;
		else l = mid + 1;
	} printf("%d", r + 1);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:28:31: 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:29:50: 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", &in[i]);
                                                  ^

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -