Submission #39372

#	Time	Username	Problem	Language	Result	Execution time	Memory
39372		14kg	Watching (JOI13_watching)	C++11	100 / 100	193 ms	16764 KiB

watching

#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][2001];

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

	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;

		dp[i][0] = dp[t2][0] + 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), X=min2(X,n), Y=min2(Y,n);
	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 (stderr)

watching.cpp: In function 'int main()':
watching.cpp:28:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &X, &Y), X=min2(X,n), Y=min2(Y,n);
                                                         ^
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: 50 / 50
• Subtask 2: 50 / 50