Submission #25420

#	Time	Username	Problem	Language	Result	Execution time	Memory
25420		kajebiii	Watching (JOI13_watching)	C++14	100 / 100	439 ms	17824 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e3 + 10;

int N, P, Q, Nr[MAX_N];
int L[2][MAX_N], Dy[MAX_N][MAX_N];
int main() {
	cin >> N >> P >> Q;
	REPO(i, N) scanf("%d", &Nr[i]);
	sort(Nr+1, Nr+N+1);

	P = min(N, P), Q = min(N, Q);

	int ans = -1;
	for(int l=1, r=1e9; l<=r; ) {
		int m = (l+r) >> 1;
		int w[2] = {m, 2*m};
		for(int k=0; k<2; k++) {
			int l = 1;
			for(int i=1; i<=N; i++) {
				while(Nr[i] - w[k] >= Nr[l]) l++;
				L[k][i] = l;
			}
		}
		Dy[0][0] = 0;
		for(int i=1; i<=N; i++) {
			for(int j=0; j<=P; j++) Dy[i][j] = INF;
			for(int j=0; j<=P; j++) {
				if(j) Dy[i][j] = min(Dy[i][j], Dy[L[0][i]-1][j-1]);
				Dy[i][j] = min(Dy[i][j], Dy[L[1][i]-1][j] + 1);
			}
		}
		bool isCan = false;
		for(int j=0; j<=P; j++) if(Dy[N][j] <= Q) isCan = true;
		if(isCan) ans = m, r = m-1;
		else l = m+1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REPO(i, N) scanf("%d", &Nr[i]);
                                ^

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