oj.uz

Submission #341440

# Submission time Handle Problem Language Result Execution time Memory
341440 2020-12-29T17:42:19 Z bigDuck Watching (JOI13_watching) C++14
50 / 100
 640 ms 31980 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=1; 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 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8556 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 424 ms 31920 KB Output is correct
4 Correct 559 ms 31852 KB Output is correct
5 Correct 100 ms 9580 KB Output is correct
6 Correct 640 ms 31980 KB Output is correct
7 Correct 78 ms 8812 KB Output is correct
8 Correct 115 ms 10476 KB Output is correct
9 Correct 272 ms 20204 KB Output is correct
10 Correct 517 ms 31980 KB Output is correct
11 Correct 104 ms 9836 KB Output is correct
12 Correct 294 ms 23828 KB Output is correct
13 Correct 84 ms 8812 KB Output is correct
14 Correct 89 ms 8684 KB Output is correct
15 Incorrect 77 ms 8812 KB Output isn't correct