Submission #197386

#	Time	Username	Problem	Language	Result	Execution time	Memory
197386		Juney	Watching (JOI13_watching)	C++14	100 / 100	748 ms	63464 KiB

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 (stderr)

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 / 50
• Subtask 2: 50 / 50