oj.uz

Submission #51479

# Submission time Handle Problem Language Result Execution time Memory
51479 2018-06-18T03:49:58 Z huynhsmd Watching (JOI13_watching) C++17
100 / 100
 325 ms 32228 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 31992 KB Output is correct
2 Correct 3 ms 31992 KB Output is correct
3 Correct 224 ms 31992 KB Output is correct
4 Correct 3 ms 31992 KB Output is correct
5 Correct 2 ms 31992 KB Output is correct
6 Correct 2 ms 31992 KB Output is correct
7 Correct 238 ms 32136 KB Output is correct
8 Correct 254 ms 32136 KB Output is correct
9 Correct 260 ms 32136 KB Output is correct
10 Correct 249 ms 32136 KB Output is correct
11 Correct 243 ms 32136 KB Output is correct
12 Correct 239 ms 32136 KB Output is correct
13 Correct 139 ms 32136 KB Output is correct
14 Correct 139 ms 32136 KB Output is correct
15 Correct 180 ms 32136 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 32136 KB Output is correct
2 Correct 2 ms 32136 KB Output is correct
3 Correct 3 ms 32136 KB Output is correct
4 Correct 2 ms 32136 KB Output is correct
5 Correct 3 ms 32136 KB Output is correct
6 Correct 2 ms 32136 KB Output is correct
7 Correct 230 ms 32212 KB Output is correct
8 Correct 249 ms 32212 KB Output is correct
9 Correct 225 ms 32212 KB Output is correct
10 Correct 258 ms 32228 KB Output is correct
11 Correct 253 ms 32228 KB Output is correct
12 Correct 325 ms 32228 KB Output is correct
13 Correct 204 ms 32228 KB Output is correct
14 Correct 219 ms 32228 KB Output is correct
15 Correct 234 ms 32228 KB Output is correct