oj.uz

Submission #283686

# Submission time Handle Problem Language Result Execution time Memory
283686 2020-08-26T05:30:05 Z aloo123 Watching (JOI13_watching) C++14
100 / 100
 503 ms 16096 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[2001];
    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<q+1;j++){
    			dp[i][j]=0;
    		}
    	}
    	int pre[n];
    	for(int i=0;i<n;i++){
    		pre[i]=(int)(lower_bound(it,it+n,it[i]+mid)-it);
    	}
    	int pre2[n];
    	for(int i=0;i<n;i++){
    		pre2[i]=(int)(lower_bound(it,it+n,it[i]+2*mid)-it);
    	}
    	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],pre[dp[i-1][j]]);
    				}
    			}
    			if(j>0){
    				if(dp[i][j-1]==n){
    					dp[i][j]=n;
    				}
    				else{
    					dp[i][j]=max(dp[i][j],pre2[dp[i][j-1]]);
    				}
    			}
    		}
    	}
    	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
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 317 ms 12184 KB Output is correct
4 Correct 43 ms 8960 KB Output is correct
5 Correct 29 ms 1024 KB Output is correct
6 Correct 503 ms 16096 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 22 ms 1280 KB Output is correct
9 Correct 23 ms 3712 KB Output is correct
10 Correct 39 ms 8704 KB Output is correct
11 Correct 34 ms 1024 KB Output is correct
12 Correct 166 ms 8108 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 8 ms 384 KB Output is correct