Submission #981278

#	Time	Username	Problem	Language	Result	Execution time	Memory
981278		Amaarsaa	Watching (JOI13_watching)	C++14	100 / 100	114 ms	16244 KiB

watching

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int N,P,Q,A[2020];
int D[2020][2020];
 
bool chk(int w)
{
	if (w <= 0) return false;
 
	int i,j,k,l;
	for (i=j=k=1;i<=N;i++){
		while (A[i] - A[j] >= w) j++;
		while (A[i] - A[k] >= w * 2) k++;
 
		D[i][0] = D[j-1][0] + 1;
		for (l=1;l<=Q;l++) D[i][l] = min(D[j-1][l] + 1, D[k-1][l-1]);
	}
 
	for (l=0;l<=Q;l++) if (D[N][l] <= P) return true;
	return false;
}
 
int main()
{
	int i;
 
	scanf ("%d %d %d",&N,&P,&Q);
	for (i=1;i<=N;i++) scanf ("%d",&A[i]);
	sort(A+1,A+1+N);
 
	if (N <= P + Q) printf ("1");
	else{
		int l = 1, r = 1000000000, m;
		while (l < r){
			m = (l + r) / 2;
			if (chk(m)) r = m - 1;
			else l = m + 1;
		}
		while (chk(m)) m--;
		while (!chk(m)) m++;
		printf ("%d",m);
	}
 
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf ("%d %d %d",&N,&P,&Q);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
watching.cpp:30:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  for (i=1;i<=N;i++) scanf ("%d",&A[i]);
      |                     ~~~~~~^~~~~~~~~~~~

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