oj.uz

Submission #976056

# Submission time Handle Problem Language Result Execution time Memory
976056 2024-05-06T06:36:10 Z vjudge1 Watching (JOI13_watching) C++17
100 / 100
 284 ms 31968 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

int nextp[2005],nextq[2005];
int a[2000+4];
int memo[2005][2005];
int n,p,q;

int dp(int idx,int p){
    if(p<0)return 1e18;
    if(idx==n+1)return 0;
    if(memo[idx][p]!=-1)return memo[idx][p];
    return memo[idx][p]=min(dp(nextp[idx],p-1),dp(nextq[idx],p)+1);
}

bool ok(int w){
    for(int k=1;k<=n;k++){
        nextp[k]=nextq[k]=n+1;
        for (int j =k+1; j <=n; j++) {
            if (a[j] - a[k] + 1 > w) {
                nextp[k] = j;
                break;
            }
        }
        for (int j = k+1; j <=n; j++) {
            if (a[j] - a[k] + 1 > 2 * w) {
                nextq[k] = j;
                break;
            }
        }
    }
    memset(memo,-1,sizeof memo);
    return dp(1,p)<=q;
}

signed main(){
    cin>>n>>p>>q;
    for(int k=1;k<=n;k++){
        cin>>a[k];
    }
    if(p+q>=n){
        cout<<1<<endl;
        return 0;
    }
    sort(a+1,a+n+1);
    int l=1,r=1e9,ans=1e9;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(mid)){
            ans=min(ans,mid);
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 31832 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 76 ms 31836 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 74 ms 31908 KB Output is correct
8 Correct 70 ms 31908 KB Output is correct
9 Correct 76 ms 31836 KB Output is correct
10 Correct 72 ms 31900 KB Output is correct
11 Correct 74 ms 31836 KB Output is correct
12 Correct 75 ms 31836 KB Output is correct
13 Correct 75 ms 31904 KB Output is correct
14 Correct 72 ms 31836 KB Output is correct
15 Correct 69 ms 31832 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 31936 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 95 ms 31928 KB Output is correct
8 Correct 109 ms 31836 KB Output is correct
9 Correct 151 ms 31968 KB Output is correct
10 Correct 284 ms 31832 KB Output is correct
11 Correct 104 ms 31936 KB Output is correct
12 Correct 245 ms 31924 KB Output is correct
13 Correct 92 ms 31832 KB Output is correct
14 Correct 90 ms 31924 KB Output is correct
15 Correct 84 ms 31928 KB Output is correct