oj.uz

Submission #341442

# Submission time Handle Problem Language Result Execution time Memory
341442 2020-12-29T17:48:33 Z bigDuck Watching (JOI13_watching) C++14
100 / 100
 577 ms 32108 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, a[300010], q, p;

int w;
int dp[2010][2010];



void dinamica(){


    for(int i=0; i<=min(n, p); i++){
        dp[0][i]=0;
    }

    for(int i=1; i<=n; i++){
        for(int j=0; j<=min(p, n);  j++){
            dp[i][j]=-1;
        }

        for(int j=i; j<=min(p, n); j++){
            dp[i][j]=dp[i-1][j-1];
        }

        int pt1=i, pt2=i;
        for(int j=i-1; j>=1; j--){
            if( (a[i]-a[j]+1)<=(w) ){
                pt1=j;
            }
            if( (a[i]-a[j]+1)<=(2*w) ){
                pt2=j;
            }
        }

        for(int j=1; j<=min(p, n); j++){
            if(dp[i][j]!=(-1)){
                if( dp[pt1-1][j-1]!=(-1) ){
                    dp[i][j]=min(dp[i][j], dp[pt1-1][j-1]);
                }
            }
            else{
                if( dp[pt1-1][j-1]!=(-1) ){
                    dp[i][j]=dp[pt1-1][j-1];
                }
            }
        }
        for(int j=0; j<=min(p, n); j++){
            if(dp[i][j]!=(-1)){
                if( (dp[pt2-1][j]!=(-1)) ){
                    dp[i][j]=min(dp[i][j], dp[pt2-1][j]+1);
                }
            }
            else{
               if( (dp[pt2-1][j]!=(-1)) ){
                    dp[i][j]=dp[pt2-1][j]+1;
               }
            }
        }
    }


}



bool verificare(){
    for(int i=0; i<=min(p, n); i++){
        if( (dp[n][i]<=q) && (dp[n][i]>(-1) ) ){
            return true;
        }
    }
    return false;
}


void cautare(){

int l=1, r=1000000001, m=(l+r)>>1ll;

while(l<r){
    m=(l+r)>>1ll;
    w=m;
    dinamica();
    if( verificare()  ){
        r=m;
    }
    else{
        l=(m+1);
    }
    m=(l+r)>>1ll;
}
w=m;

}









int32_t main(){
INIT
cin>>n>>p>>q;
for(int i=1; i<=n; i++){
    cin>>a[i];
}
sort(a+1, a+n+1);
cautare();
cout<<w;


return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 8556 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 452 ms 31852 KB Output is correct
4 Correct 577 ms 31980 KB Output is correct
5 Correct 99 ms 9580 KB Output is correct
6 Correct 571 ms 31852 KB Output is correct
7 Correct 79 ms 8812 KB Output is correct
8 Correct 108 ms 10476 KB Output is correct
9 Correct 262 ms 20204 KB Output is correct
10 Correct 555 ms 32108 KB Output is correct
11 Correct 102 ms 9836 KB Output is correct
12 Correct 316 ms 23788 KB Output is correct
13 Correct 82 ms 8556 KB Output is correct
14 Correct 79 ms 8768 KB Output is correct
15 Correct 80 ms 8684 KB Output is correct