Submission #1238965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238965		maomao	Watching (JOI13_watching)	C++17	100 / 100	157 ms	16272 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int n, p, q, sz;
int dp[2005][2005]{}; //dp[small cameras used][large cameras used] = max index covered so far
int a[2005] {};
bool check(int w) {
	for(int i = 0; i<=p; i++) {
		for(int j = 0; j<=q; j++) {
			int pos = dp[i][j]+1, next;
			//small cam
			if(i!=p) {
			next = pos;
			while(next < sz) {
				if(a[next+1] - a[pos] <= w-1) next++;
				else break;
			}
			dp[i+1][j] = max(dp[i+1][j], min(sz,next));
			}
			
			//large cam
			if(j!=q){
			next = pos;
			while(next<sz) {
				if(a[next+1] - a[pos] <= 2*w-1) next++;
				else break;
			}
			dp[i][j+1] = max(dp[i][j+1], min(next,sz));
			}
			
			
		}
	}
	return (dp[p][q] == sz);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> p >> q;
	set<int> sec; 
	for(int i = 0; i<n; i++) {
		int a; cin >> a;
		sec.insert(a);
	}
	if(p+q >= n) {
		cout << 1;
		return 0;
	}
	int i = 1;
	for(int k : sec) {
		a[i] = k; i++;
	}
	sz = i-1;
	int l = 1, r = *sec.rbegin(), ans;
	while(l<=r) {
		memset(dp, 0, sizeof(dp));
		int w = (l+r)/2;
		if(check(w)) {
			ans = w; 
			r = w-1;
		} else l = w+1;
	}
	cout << ans;
	return 0;
}

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