oj.uz

Submission #51478

# Submission time Handle Problem Language Result Execution time Memory
51478 2018-06-18T03:48:15 Z huynhsmd Watching (JOI13_watching) C++17
100 / 100
 370 ms 32252 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(int j = i ; j <= n ; ++ j){
			if(a[j] - a[i] + 1 <= mid) Maxw[i] = j;
			if(a[j] - a[i] + 1 <= 2*mid) Max2w[i] = j;
		}
		/*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;
}

Compilation message

watching.cpp: In function 'bool check(long long int)':
watching.cpp:13:6: warning: unused variable 'cur1' [-Wunused-variable]
  int cur1 = 1, cur2 = 1;
      ^~~~
watching.cpp:13:16: warning: unused variable 'cur2' [-Wunused-variable]
  int cur1 = 1, cur2 = 1;
                ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 31956 KB Output is correct
2 Correct 2 ms 31956 KB Output is correct
3 Correct 235 ms 31976 KB Output is correct
4 Correct 2 ms 31976 KB Output is correct
5 Correct 3 ms 31976 KB Output is correct
6 Correct 2 ms 31976 KB Output is correct
7 Correct 229 ms 32236 KB Output is correct
8 Correct 244 ms 32236 KB Output is correct
9 Correct 224 ms 32236 KB Output is correct
10 Correct 228 ms 32236 KB Output is correct
11 Correct 233 ms 32236 KB Output is correct
12 Correct 229 ms 32236 KB Output is correct
13 Correct 134 ms 32236 KB Output is correct
14 Correct 132 ms 32236 KB Output is correct
15 Correct 173 ms 32252 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 32252 KB Output is correct
2 Correct 2 ms 32252 KB Output is correct
3 Correct 2 ms 32252 KB Output is correct
4 Correct 3 ms 32252 KB Output is correct
5 Correct 3 ms 32252 KB Output is correct
6 Correct 3 ms 32252 KB Output is correct
7 Correct 329 ms 32252 KB Output is correct
8 Correct 341 ms 32252 KB Output is correct
9 Correct 322 ms 32252 KB Output is correct
10 Correct 326 ms 32252 KB Output is correct
11 Correct 305 ms 32252 KB Output is correct
12 Correct 370 ms 32252 KB Output is correct
13 Correct 244 ms 32252 KB Output is correct
14 Correct 256 ms 32252 KB Output is correct
15 Correct 316 ms 32252 KB Output is correct