oj.uz

Submission #465015

# Submission time Handle Problem Language Result Execution time Memory
465015 2021-08-14T20:34:50 Z Blobo2_Blobo2 Watching (JOI13_watching) C++14
100 / 100
 978 ms 16072 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 idx){
    int s=idx,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 INT_MAX;
    if(idx>=n)
        return 0;
    int &ret = dp[idx][small];
    if(ret!=-1)return ret;
    ret=INT_MAX;
    int r1 = (arr[idx] + mid) -1 ,r2 = (arr[idx] + (mid*2)) -1;
    int idx2 = BS(r1,idx),idx3 = BS(r2,idx);
    return ret = min(check(idx2+1,small+1),
                        check(idx3+1,small)+1);
}

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

Compilation message

watching.cpp:19:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int mo=1e9+7,INF=1e18;
      |                        ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 732 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8268 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 7 ms 8448 KB Output is correct
8 Correct 104 ms 9356 KB Output is correct
9 Correct 408 ms 14260 KB Output is correct
10 Correct 978 ms 16068 KB Output is correct
11 Correct 106 ms 9284 KB Output is correct
12 Correct 737 ms 16072 KB Output is correct
13 Correct 5 ms 8396 KB Output is correct
14 Correct 5 ms 8396 KB Output is correct
15 Correct 6 ms 8396 KB Output is correct