Submission #197386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
197386	2020-01-20T17:03:07 Z	Juney	Watching (JOI13_watching)	C++14	100 / 100	748 ms	63464 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++) {
		int idx1 = upper_bound(A+1, A+1+N, A[i] + w-1) - A;
		int idx2 = upper_bound(A+1, A+1+N, A[i] + 2*w-1) - A;
		for(int j=1; j<=P+2*Q; j++) {
			if(D[0][i][j] > 0) {
				if(D[0][idx1][j-1] < D[0][i][j]-1) {
					D[0][idx1][j-1] = D[0][i][j]-1;
					D[1][idx1][j-1] = D[1][i][j];
				}
			}
			if(D[1][i][j] > 0) {
				if(D[0][idx2][j-2] < D[0][i][j]) {
					D[0][idx2][j-2] = D[0][i][j];
					D[1][idx2][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	388 ms	63324 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	382 ms	63352 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	385 ms	63316 KB	Output is correct
8	Correct	372 ms	63352 KB	Output is correct
9	Correct	402 ms	63224 KB	Output is correct
10	Correct	377 ms	63224 KB	Output is correct
11	Correct	388 ms	63352 KB	Output is correct
12	Correct	387 ms	63324 KB	Output is correct
13	Correct	403 ms	63320 KB	Output is correct
14	Correct	375 ms	63324 KB	Output is correct
15	Correct	488 ms	63388 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	438 ms	63376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	404 ms	63356 KB	Output is correct
8	Correct	562 ms	63352 KB	Output is correct
9	Correct	507 ms	63352 KB	Output is correct
10	Correct	647 ms	63452 KB	Output is correct
11	Correct	748 ms	63352 KB	Output is correct
12	Correct	685 ms	63224 KB	Output is correct
13	Correct	404 ms	63352 KB	Output is correct
14	Correct	451 ms	63464 KB	Output is correct
15	Correct	448 ms	63352 KB	Output is correct