Submission #797859

#	Time	Username	Problem	Language	Result	Execution time	Memory
797859		OrazB	Watching (JOI13_watching)	C++14	100 / 100	257 ms	8148 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()

const int N = 2e3+5;
int a[N];

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, p, q;
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	if (p+q >= n) return cout << 1, 0;
	int l = 1, r = 1e9, ans = -1;
	while(l <= r){
		int md = (l+r)>>1;
		vector<vector<int>> dp(n+1, vector<int>(min(p+1,q+1), 1e9));
		for (int i = 0; i <= min(p,q); i++) dp[0][i] = 0;
		int pos1 = 1, pos2 = 1;
		for (int i = 1; i <= n; i++){
			for (int j = 0; j <= min(p,q); j++){
				while(a[pos1] <= a[i]-md) pos1++;
				while(a[pos2] <= a[i]-2*md) pos2++;
				if (p <= q){
					if (j) dp[i][j] = min(dp[i][j], dp[pos1-1][j-1]);
					dp[i][j] = min(dp[i][j], dp[pos2-1][j]+1);
				}else{
					if (j) dp[i][j] = min(dp[i][j], dp[pos2-1][j-1]);
					dp[i][j] = min(dp[i][j], dp[pos1-1][j]+1);
				}
			}
		}
		if (*min_element(all(dp[n])) <= max(p,q)){
			ans = md;
			r = md - 1;
		}else l = md + 1;
	}
	cout << ans;
}	

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