Submission #51479

#	Time	Username	Problem	Language	Result	Execution time	Memory
51479		huynhsmd	Watching (JOI13_watching)	C++17	100 / 100	325 ms	32228 KiB

watching

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N = 2005;

int  n , p , q , ans;
int a[N] , cnt[N] , Max2w[N]  ,Maxw[N];
int f[N][N];

bool check(int mid){
	int cur1 = 1, cur2 = 1;
	for(int i = 1 ; i <= n ; ++ i){
		for(;cur1 <= n && a[cur1] - a[i] + 1 <= mid ; ++ cur1);
		Maxw[i] = cur1 - 1;
		for(;cur2 <= n && a[cur2] - a[i] + 1 <= 2*mid ; ++ cur2);
		Max2w[i] = cur2 - 1;
	}
	memset(f,-1,sizeof f);
	f[1][0] = Maxw[1]; 
	f[0][1] = Max2w[1];
	if(Maxw[1] == n || Max2w[1] == n) return true;
	for(int i = 0 ; i <= p ; ++ i)
		for(int j = 0 ; j <= q ; ++ j)
			if(f[i][j] != -1){
				if(f[i][j] == n) return true;	
				f[i][j + 1] = max(f[i][j + 1] , Max2w[f[i][j] + 1]);
				f[i + 1][j] = max(f[i + 1][j] , Maxw[f[i][j] + 1]);
			}
	return false;
}
signed main(){
	//freopen("1.inp","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	a[n+1] = 1e9;
	for(int i = 1 ;i <= n ; ++ i )
		cin >> a[i];
	sort(a + 1 , a + n + 1);	
	if( p+q >= n ){
		cout << 1;
		return 0;
	}	
	int l = 1 , r = a[n] - a[1] + 1;
	while(l <= r){
		int mid = ( l + r ) / 2;
		bool kt = check(mid);
		if(kt){
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans;
}

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