oj.uz

Submission #445554

# Submission time Handle Problem Language Result Execution time Memory
445554 2021-07-18T16:31:57 Z julian33 Watching (JOI13_watching) C++14
100 / 100
 271 ms 16196 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=2e3+5; //make sure this is right
const int mod=1e9+7;

int dp[mxN][mxN],a[mxN],n,p,q;

bool check(int k){
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        int go=lower_bound(a,a+1+n,a[i]-k+1)-a;
        int go2=lower_bound(a,a+1+n,a[i]-2*k+1)-a;
        if(go) go--;
        if(go2) go2--;
        for(int j=1;j<=p;j++){
            if(dp[go][j-1]!=-1)
                dp[i][j]=dp[i][j]==-1?dp[go][j-1]:min(dp[i][j],dp[go][j-1]);
            if(dp[go2][j]!=-1 && dp[go2][j]<q)
                dp[i][j]=dp[i][j]==-1?dp[go2][j]+1:min(dp[i][j],dp[go2][j]+1);
        }
        if(dp[go2][0]!=-1 && dp[go2][0]<q)
            dp[i][0]=dp[i][0]==-1?dp[go2][0]+1:min(dp[i][0],dp[go2][0]+1);
    }
    for(int i=0;i<=p;i++){
        if(dp[n][i]!=-1)
            return 1;
    }
    return 0;
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    cin>>n>>p>>q;
    mina(p,n); mina(q,n);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a,a+1+n);
    int l=1; int r=1e9;
    int ans=1e9;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid; r=mid-1;
        } else{
            l=mid+1;
        }
    }
    cout<<ans<<"\n";
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16120 KB Output is correct
2 Correct 67 ms 16012 KB Output is correct
3 Correct 69 ms 16032 KB Output is correct
4 Correct 67 ms 16036 KB Output is correct
5 Correct 66 ms 16036 KB Output is correct
6 Correct 65 ms 15948 KB Output is correct
7 Correct 68 ms 16044 KB Output is correct
8 Correct 67 ms 15948 KB Output is correct
9 Correct 67 ms 15948 KB Output is correct
10 Correct 66 ms 15948 KB Output is correct
11 Correct 70 ms 16032 KB Output is correct
12 Correct 69 ms 15948 KB Output is correct
13 Correct 70 ms 16076 KB Output is correct
14 Correct 68 ms 15948 KB Output is correct
15 Correct 67 ms 15948 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 16076 KB Output is correct
2 Correct 64 ms 15948 KB Output is correct
3 Correct 221 ms 16068 KB Output is correct
4 Correct 239 ms 15948 KB Output is correct
5 Correct 80 ms 16196 KB Output is correct
6 Correct 271 ms 16076 KB Output is correct
7 Correct 76 ms 16076 KB Output is correct
8 Correct 88 ms 15948 KB Output is correct
9 Correct 148 ms 16052 KB Output is correct
10 Correct 246 ms 16076 KB Output is correct
11 Correct 83 ms 16076 KB Output is correct
12 Correct 199 ms 15948 KB Output is correct
13 Correct 78 ms 16076 KB Output is correct
14 Correct 76 ms 16076 KB Output is correct
15 Correct 76 ms 16076 KB Output is correct