Submission #197385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
197385	2020-01-20T17:00:34 Z	Juney	Watching (JOI13_watching)	C++14	50 / 100	1000 ms	63436 KB

watching

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e3 + 5;

int N, A[MAXN], P, Q;
int D[2][MAXN][2*MAXN];

bool can(int w) {
	memset(D, -1, sizeof(D));
	D[0][1][P+2*Q] = P;
	D[1][1][P+2*Q] = Q;
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=P+2*Q; j++) {
			if(D[0][i][j] > 0) {
				int idx = upper_bound(A+1, A+1+N, A[i] + w-1) - A;
				if(D[0][idx][j-1] < D[0][i][j]-1) {
					D[0][idx][j-1] = D[0][i][j]-1;
					D[1][idx][j-1] = D[1][i][j];
				}
			}
			if(D[1][i][j] > 0) {
				int idx = upper_bound(A+1, A+1+N, A[i] + 2*w-1) - A;
				if(D[0][idx][j-2] < D[0][i][j]) {
					D[0][idx][j-2] = D[0][i][j];
					D[1][idx][j-2] = D[1][i][j]-1;
				}
			}
		}
	}
	for(int i=0; i<=P+2*Q; i++) if(D[0][N+1][i] != -1) return 1;
	return 0;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> P >> Q;
	for(int i=1; i<=N; i++) cin >> A[i];
	sort(A+1, A+1+N);
	if(P + Q >= N) {
		cout << 1;
		return 0;
	}
	int l = 1, r = 1e9, ans;
	while(l <= r) {
		int mid = l + r >> 1;
		if(can(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
watching.cpp:60:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << ans;
  ~~~~~^~~~~~

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	381 ms	63352 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	387 ms	63356 KB	Output is correct
4	Correct	2 ms	372 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	383 ms	63352 KB	Output is correct
8	Correct	372 ms	63352 KB	Output is correct
9	Correct	384 ms	63224 KB	Output is correct
10	Correct	374 ms	63224 KB	Output is correct
11	Correct	387 ms	63352 KB	Output is correct
12	Correct	418 ms	63352 KB	Output is correct
13	Correct	385 ms	63352 KB	Output is correct
14	Correct	425 ms	63436 KB	Output is correct
15	Correct	393 ms	63352 KB	Output is correct

Subtask #2

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	386 ms	63340 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	396 ms	63356 KB	Output is correct
8	Correct	660 ms	63352 KB	Output is correct
9	Correct	550 ms	63384 KB	Output is correct
10	Correct	673 ms	63352 KB	Output is correct
11	Correct	872 ms	63352 KB	Output is correct
12	Execution timed out	1085 ms	63224 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-