Submission #238598

#	Time	Username	Problem	Language	Result	Execution time	Memory
238598		maomao90	Watching (JOI13_watching)	C++14	100 / 100	953 ms	16348 KiB

watching

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 1000000005

int N, P, Q;
int A[2005];
int ans;

int memo[2005][2005];
int getMinQ(int i, int remP, int v) {
	if (i >= N) return 0;
	if (memo[i][remP] != -1) return memo[i][remP];
	int pNext = upper_bound(A + i, A + N, A[i] + v - 1) - A;
	int qNext = upper_bound(A + i, A + N, A[i] + 2 * v - 1) - A;
	// if (v == 9) printf("%d: %d, %d\n", i, pNext, qNext);
	if (remP == 0) return memo[i][remP] = getMinQ(qNext, remP, v) + 1;
	return memo[i][remP] = min(getMinQ(pNext, remP - 1, v), getMinQ(qNext, remP, v) + 1);
}

bool isPossible(int v) {
	memset(memo, -1, sizeof memo);
	// printf("%d: %d\n", v, getMinQ(0, P, v));
	return getMinQ(0, P, v) <= Q;
}

int main() {
	scanf("%d%d%d", &N, &P, &Q);
	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);
	if (P + Q >= N) {
		printf("1\n");
		return 0;
	}
	sort(A, A + N);
	int lo = 2, hi = INF, mid;
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (isPossible(mid)) {
			hi = mid - 1;
			ans = mid;
		} else lo = mid + 1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:31: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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~

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