oj.uz

Submission #230735

# Submission time Handle Problem Language Result Execution time Memory
230735 2020-05-11T13:44:04 Z kshitij_sodani Watching (JOI13_watching) C++17
0 / 100
 1000 ms 12160 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
//typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
int it[1000001];
int dp[2001][2001];
int n,p,q;
bool check(int mid){
	for(int i=0;i<p+1;i++){
		for(int j=0;j<p+1;j++){
			dp[i][j]=0;
		}
	}
	for(int i=0;i<p+1;i++){
		for(int j=0;j<q+1;j++){
			if(i==0 and j==0){
				continue;
			}
			if(i>0){
				if(dp[i-1][j]==n){
					dp[i][j]=n;
				}
				else{
					dp[i][j]=max(dp[i][j],(int)(lower_bound(it,it+n,it[dp[i-1][j]]+mid)-it));
				}
			}
			if(j>0){
				if(dp[i][j-1]==n){
					dp[i][j]=n;
				}
				else{
					dp[i][j]=max(dp[i][j],(int)(lower_bound(it,it+n,it[dp[i][j-1]]+2*mid)-it));
				}
			}
		}
	}
	return dp[p][q]>=(n);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>p>>q;
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	sort(it,it+n);
	p=min(p,n);
	q=min(q,n);
	int low=1;
	int high=1000000000;
	while(low<high-1){
		int mid=(low+high)/2;
		if(check(mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	int ans=high;
	if(check(low)){
		ans=min(ans,low);
	}
	cout<<ans<<endl;



	return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

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