oj.uz

Submission #635582

# Submission time Handle Problem Language Result Execution time Memory
635582 2022-08-26T13:22:06 Z urosk Watching (JOI13_watching) C++14
100 / 100
 651 ms 31756 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 2005
ll n,p,q;
ll a[maxn];
ll dp[maxn][maxn];
ll bs(ll i,ll w){
    ll l = i,r = n,mid,rez = i;
    while(l<=r){
        mid = (l+r)/2;
        if(a[mid]-a[i]+1<=w) l = mid+1,rez = mid;
        else r = mid-1;
    }
    return rez;
}
bool moe(ll w){
    for(ll i = 0;i<=n;i++) for(ll j = 0;j<=n;j++) dp[i][j] = 0;
    dp[0][0] = 0;
    for(ll i = 0;i<=p;i++){
        for(ll j = 0;j<=q;j++){
            dp[i+1][j] = max(dp[i+1][j],bs(dp[i][j]+1,w));
            dp[i][j+1] = max(dp[i][j+1],bs(dp[i][j]+1,2*w));
        }
    }
    return dp[p][q]>=n;
}
int main(){
	daj_mi_malo_vremena
    cin >> n >> p >> q;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    sort(a+1,a+1+n);
    if(p+q>=n){cout<<1<<endl; return 0;}
    ll l = 1,r = 1e9,mid,rez = 1e9;
    while(l<=r){
        mid = (l+r)/2;
        if(moe(mid)) r = mid-1,rez = mid;
        else l = mid+1;
    }
    cout<<rez<<endl;
	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 720 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 31656 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 123 ms 31736 KB Output is correct
8 Correct 201 ms 31628 KB Output is correct
9 Correct 191 ms 31752 KB Output is correct
10 Correct 215 ms 31752 KB Output is correct
11 Correct 221 ms 31748 KB Output is correct
12 Correct 651 ms 31752 KB Output is correct
13 Correct 119 ms 31724 KB Output is correct
14 Correct 115 ms 31748 KB Output is correct
15 Correct 114 ms 31756 KB Output is correct