oj.uz

Submission #464994

# Submission time Handle Problem Language Result Execution time Memory
464994 2021-08-14T20:11:29 Z Blobo2_Blobo2 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 36292 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);

const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}
int n,sm,big,arr[2001],dp[2001][2001],mid;
int BS(int x){
    int s=0,e=n-1;
    while(s<=e){
        int mid=(s+e)>>1;
        if(arr[mid]>x)e=mid-1;
        else s=mid+1;
    }
    return e;
}
int check(int idx=0,int small=0){
    if(small>sm)
        return 1e10;
    if(idx>=n)
        return 0;
    int &ret = dp[idx][small];
    if(ret!=-1)return ret;
    ret=1e10;
    int r1 = (arr[idx] + mid) -1 ,r2 = (arr[idx] + (mid*2)) -1;
    int idx2 = BS(r1),idx3 = BS(r2);
    return ret = min(check(idx2+1,small+1),
                        check(idx3+1,small)+1);
}

bool ok(){
    memset(dp,-1,sizeof dp);
    check();
    for(int i=0;i<=sm;i++){
        if(dp[0][i]<=big&&dp[0][i]!=-1)return 1;
    }
    return 0;
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    n=nxt(),sm=nxt(),big=nxt();
    gen(arr,n,nxt);
    sort(arr,arr+n);
    int s=0,e=1e9,mn=1e9;
    while(s<=e){
        //if(e==1)break;
        mid=(s+e)>>1;
        if(ok()){
            mn=min(mn,mid);
            e=mid-1;
        }
        else s=mid+1;
    }
    cout<<mn;
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 31640 KB Output is correct
2 Correct 120 ms 31564 KB Output is correct
3 Correct 121 ms 31644 KB Output is correct
4 Correct 130 ms 36292 KB Output is correct
5 Correct 127 ms 31540 KB Output is correct
6 Correct 131 ms 36252 KB Output is correct
7 Correct 123 ms 31560 KB Output is correct
8 Correct 126 ms 31664 KB Output is correct
9 Correct 124 ms 31684 KB Output is correct
10 Correct 122 ms 31636 KB Output is correct
11 Correct 124 ms 31648 KB Output is correct
12 Correct 126 ms 31684 KB Output is correct
13 Correct 122 ms 31640 KB Output is correct
14 Correct 122 ms 31636 KB Output is correct
15 Correct 123 ms 31564 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 31664 KB Output is correct
2 Correct 128 ms 31564 KB Output is correct
3 Execution timed out 1088 ms 31864 KB Time limit exceeded
4 Halted 0 ms 0 KB -