oj.uz

Submission #1093160

# Submission time Handle Problem Language Result Execution time Memory
1093160 2024-09-26T04:20:39 Z bobweasley Watching (JOI13_watching) C++17
0 / 100
 39 ms 64364 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define base 101
using namespace std;

const ll mxN = 2005;
const ll mx = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int n,p,q;
ll dp[mxN][mxN];
vector<ll> a;
int res;

bool check(int x){
    memset(dp,-1,sizeof(dp));
    for(int i = 0;i <= p; i++){
        for(int j = 0;j <= q;j++){
            if(i == 0 && j == 0) continue;

            ll i1 = dp[i][j-1] + 1;
            ll i2 = dp[i-1][j] + 1;
            ll cur1 = a[i1] + (2*x) - 1;
            ll cur2 = a[i2] + x - 1;
            ll k1 = upper_bound(a.begin(),a.end(),cur1) - a.begin() - 1;
            ll k2 = upper_bound(a.begin(),a.end(),cur2) - a.begin() - 1;

            if(i == 0) dp[i][j] = k1;
            else if(j == 0) dp[i][j] = k2;
            else dp[i][j] = max(k1,k2);

            if(dp[i][j] >= n-1) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>p>>q;
    for(int i = 0;i < n;i++){
        ll t; cin>>t;
        a.push_back(t);
    }
    ll l = 1,r = 1e9;
    res = r;
    p = min(p,n);
    q = min(q,n);
    if(p+q >= n){
        cout<<1;
        return 0;
    }
    sort(a.begin(),a.end());
    while(l <= r){
        int mid = (l + r)/2;

        if(check(mid)){
            res = min(res,mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout<<res;

    return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 64364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 64336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -