제출 #1251817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251817		random_name	Watching (JOI13_watching)	C++20	100 / 100	845 ms	8000 KiB

watching

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, p, q;
vector<ll> A;

bool can_build(ll w){
    ll p_range = w, q_range = 2*w;

    vector<vector<ll>> max_n(p+1, vector<ll>(q+1));

    for(ll i = 0; i <= p; i++){
        for(ll j = 0; j <= q; j++){
            ll up=0, left=0;

            if(j != 0){
                up = lower_bound(A.begin(), A.end(), A[max_n[i][j-1]] + q_range) - A.begin();
            }

            if(i != 0){
                left = lower_bound(A.begin(), A.end(), A[max_n[i-1][j]] + p_range) - A.begin();
            }

            max_n[i][j] = max(up, left);
            if(max_n[i][j] >= n){
                return true;
            }
        }
    }

    return false;
}

int main(){
    cin >> n >> p >> q;
    A.resize(n);
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }

    if(p + q >= n){
        cout << 1;
        return 0;
    }

    sort(A.begin(), A.end());

    ll l=0, r=1000000010;
    while(l != r){
        ll m = (l+r-1) / 2;
        if(can_build(m)){
            r = m;
        }

        else{
            l = m+1;
        }
    }

    cout << l;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50