oj.uz

Submission #465004

# Submission time Handle Problem Language Result Execution time Memory
465004 2021-08-14T20:23:01 Z Hamed5001 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 36368 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;}
long long n,sm,big,arr[2001],dp[2001][2001],mid;
long long 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;
}
long long check(int idx=0,int small=0){
    if(small>sm)
        return 1e10;
    if(idx>=n)
        return 0;
    long long &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 124 ms 31636 KB Output is correct
2 Correct 123 ms 31640 KB Output is correct
3 Correct 129 ms 31636 KB Output is correct
4 Correct 132 ms 36244 KB Output is correct
5 Correct 124 ms 31636 KB Output is correct
6 Correct 130 ms 36368 KB Output is correct
7 Correct 129 ms 31564 KB Output is correct
8 Correct 123 ms 31636 KB Output is correct
9 Correct 126 ms 31596 KB Output is correct
10 Correct 126 ms 31648 KB Output is correct
11 Correct 124 ms 31632 KB Output is correct
12 Correct 129 ms 31540 KB Output is correct
13 Correct 131 ms 31636 KB Output is correct
14 Correct 128 ms 31636 KB Output is correct
15 Correct 129 ms 31640 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 31648 KB Output is correct
2 Correct 125 ms 31640 KB Output is correct
3 Execution timed out 1094 ms 31808 KB Time limit exceeded
4 Halted 0 ms 0 KB -