oj.uz

Submission #51477

# Submission time Handle Problem Language Result Execution time Memory
51477 2018-06-18T03:46:48 Z mergesort Watching (JOI13_watching) C++14
100 / 100
 282 ms 16512 KB 
#include<bits/stdc++.h>
using namespace std;
int a[2005],n,p,q;
int len1[2005],len2[2005],dp[2005][2005];
bool check(int w)
{
    for(int i=1;i<=n;++i){
        len1[i]=len2[i]=i;
        for(int j=i+1;j<=n;++j){
            if(a[i]+w-1>=a[j])len1[i]=j;
            if(a[i]+2*w-1>=a[j])len2[i]=j;
        }
    }
    len1[n+1]=len2[n+1]=n;
    memset(dp,-1,sizeof dp);
    dp[0][0]=0;
    for(int i=0;i<=p;++i){
        for(int j=0;j<=q;++j){
            if(i==0 && j==0)continue;
            if(i==0 && j){
                dp[i][j]=max(dp[i][j],len2[dp[i][j-1]+1]);
                continue;
            }
            else if(i && j==0){
                dp[i][j]=max(dp[i][j],len1[dp[i-1][j]+1]);
                continue;
            }
            int pos1=dp[i-1][j],pos2=dp[i][j-1];
            if(pos1>=n || pos2>=n){
                dp[i][j]=n;
                return true;
            }
            pos1++;
            pos2++;
            dp[i][j]=max(len1[pos1],len2[pos2]);
            if(dp[i][j]>=n)return true;
        }
    }
    if(dp[p][q]>=n)return true;
    else return false;
}
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+1+n);
    if(p+q>=n){
        cout<<"1";
        return 0;
    }
    int l=0,r=1e9;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    //cout<<check(4)<<"\n****"<<endl;
    int ans=1e9;
    if(check(r))ans=min(ans,r);
    if(check(l))ans=min(ans,l);
    cout<<ans;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 16184 KB Output is correct
2 Correct 2 ms 16184 KB Output is correct
3 Correct 42 ms 16184 KB Output is correct
4 Correct 2 ms 16184 KB Output is correct
5 Correct 2 ms 16184 KB Output is correct
6 Correct 2 ms 16184 KB Output is correct
7 Correct 45 ms 16228 KB Output is correct
8 Correct 92 ms 16232 KB Output is correct
9 Correct 45 ms 16416 KB Output is correct
10 Correct 45 ms 16416 KB Output is correct
11 Correct 51 ms 16416 KB Output is correct
12 Correct 105 ms 16416 KB Output is correct
13 Correct 56 ms 16416 KB Output is correct
14 Correct 124 ms 16416 KB Output is correct
15 Correct 77 ms 16416 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 16416 KB Output is correct
2 Correct 4 ms 16416 KB Output is correct
3 Correct 3 ms 16416 KB Output is correct
4 Correct 4 ms 16416 KB Output is correct
5 Correct 3 ms 16416 KB Output is correct
6 Correct 3 ms 16416 KB Output is correct
7 Correct 180 ms 16416 KB Output is correct
8 Correct 229 ms 16416 KB Output is correct
9 Correct 231 ms 16484 KB Output is correct
10 Correct 219 ms 16492 KB Output is correct
11 Correct 208 ms 16492 KB Output is correct
12 Correct 282 ms 16492 KB Output is correct
13 Correct 214 ms 16512 KB Output is correct
14 Correct 169 ms 16512 KB Output is correct
15 Correct 166 ms 16512 KB Output is correct