oj.uz

Submission #51476

# Submission time Handle Problem Language Result Execution time Memory
51476 2018-06-18T03:45:40 Z futanaristic Watching (JOI13_watching) C++14
100 / 100
 309 ms 32124 KB 
#include <bits/stdc++.h>
#define INF 1000000007
#define pb push_back
#define int long long
#define ub upper_bound
using namespace std;
int n,p,q,a[2001],S[2001],B[2001],dp[2001][2001];
bool legit(int W) {
	for (int i = 0 ; i < n ; i ++) {
		S[i]=ub(a,a+n,a[i]+W-1)-a;
		B[i]=ub(a,a+n,a[i]+2*W-1)-a;
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;  
	for (int i = 0 ; i <= p ; i ++)
	for (int j = 0 ; j <= q ; j ++) 
	if (dp[i][j]!=-1) {
		if (dp[i][j]==n) return true;
		dp[i+1][j]=max(dp[i+1][j],S[dp[i][j]]);
		dp[i][j+1]=max(dp[i][j+1],B[dp[i][j]]);
	}
	return false;
}

signed main() {
	
	cin >> n>>p>>q;
	for (int i = 0 ; i < n ; i ++) cin>>a[i]; 
	if (p+q>=n) {cout<<"1"; return 0;}
	sort(a,a+n);
	int L = 1 ,R = 1000000000;
	while(L <= R){
		if (L == R)break;
		int M = L + (R-L)/2;
		if(legit(M)) R = M;
		else L = M + 1;
	} 
	cout << L;
	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 31736 KB Output is correct
2 Correct 2 ms 31736 KB Output is correct
3 Correct 226 ms 31928 KB Output is correct
4 Correct 2 ms 31928 KB Output is correct
5 Correct 2 ms 31928 KB Output is correct
6 Correct 2 ms 31928 KB Output is correct
7 Correct 230 ms 31928 KB Output is correct
8 Correct 244 ms 32052 KB Output is correct
9 Correct 221 ms 32052 KB Output is correct
10 Correct 232 ms 32052 KB Output is correct
11 Correct 209 ms 32068 KB Output is correct
12 Correct 210 ms 32068 KB Output is correct
13 Correct 215 ms 32068 KB Output is correct
14 Correct 224 ms 32068 KB Output is correct
15 Correct 230 ms 32068 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 32068 KB Output is correct
2 Correct 2 ms 32068 KB Output is correct
3 Correct 3 ms 32068 KB Output is correct
4 Correct 3 ms 32068 KB Output is correct
5 Correct 3 ms 32068 KB Output is correct
6 Correct 3 ms 32068 KB Output is correct
7 Correct 222 ms 32100 KB Output is correct
8 Correct 268 ms 32100 KB Output is correct
9 Correct 258 ms 32100 KB Output is correct
10 Correct 237 ms 32100 KB Output is correct
11 Correct 232 ms 32100 KB Output is correct
12 Correct 309 ms 32100 KB Output is correct
13 Correct 232 ms 32124 KB Output is correct
14 Correct 225 ms 32124 KB Output is correct
15 Correct 236 ms 32124 KB Output is correct