oj.uz

Submission #107680

# Submission time Handle Problem Language Result Execution time Memory
107680 2019-04-25T12:31:54 Z maruii Watching (JOI13_watching) C++14
50 / 100
 1000 ms 12284 KB 
#include <bits/stdc++.h>
using namespace std;
int N, P, Q;
unsigned A[2002];
int dp[2001][2001];
int f(int w){
	for(int i=0; i<=P; ++i){
		for(int j=0; j<=Q; ++j){
			if(i && j) dp[i][j] = max(lower_bound(A+1, A+N+1, A[dp[i-1][j] + 1] + w), lower_bound(A+1, A+N+1, A[dp[i][j-1] + 1] + (w<<1))) - A - 1;
			else if(i) dp[i][j] = lower_bound(A+1, A+N+1, A[dp[i-1][j] + 1] + w) - A - 1;
			else if(j) dp[i][j] = lower_bound(A+1, A+N+1, A[dp[i][j-1] + 1] + (w<<1)) - A - 1;
		}
	}
	return dp[P][Q];
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin>>N>>P>>Q;
	for(int i=1; i<=N; ++i) cin>>A[i];
	sort(A+1, A+N+1);
	A[N+1] = 2e9;
	P = min(P, N), Q = min(Q, N);
	int l=1, r=1e9;
	while(l<r){
		int m = l+r>>1;
		if(f(m) == N) r = m;
		else l = m+1;
	}
	cout<<l;
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l+r>>1;
           ~^~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 768 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Execution timed out 1068 ms 12284 KB Time limit exceeded
4 Halted 0 ms 0 KB -