Submission #51418

#	Time	Username	Problem	Language	Result	Execution time	Memory
51418		FutymyClone	Watching (JOI13_watching)	C++14	100 / 100	269 ms	16844 KiB

watching

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 7;
int L = 0, R = 1e9 + 1, n, p, q, a[2010], dp[2010][2010], W;

bool check(int w) {
	for(int i = 0; i <= p; i++) dp[0][i] = 0;
	dp[0][0] = 1, W = 2*w;
	int l1 = 0, l2 = 0, r = 1;
	while(r < n) {
		dp[r][0] = inf;
		while(l1 < r && a[l1] + w - 1 < a[r]) l1++;
		for(int i = 1; i <= p; i++) dp[r][i] = (l1 ? dp[l1-1][i-1] : 0);
		while(l2 < r && a[l2] + W - 1 < a[r]) l2++;
		for(int i = 0; i <= p; i++) dp[r][i] = min(dp[r][i], (l2 ? dp[l2-1][i] + 1 : 1));
		r++;
	}
	return (dp[n-1][p] <= q);
}

int main() {
	scanf("%d%d%d", &n, &p, &q);
	if(p >= n) {
		printf("1\n");
		return 0;
	}
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	sort(a, a + n);
	while(L + 1 < R) {
		int M =(L + R)/2;
		if(check(M)) R = M;
		else L = M;
	}
	printf("%d", R);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:23:7: 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:28:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
                             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50