Submission #1205931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205931		minhpk	Watching (JOI13_watching)	C++20	0 / 100	0 ms	396 KiB

watching

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int a, b, c;
vector<ll> z;
int K;

int count_segments(int w, vector<pair<int,int>>& segs){
    segs.clear();
    int i = 0; 
    while(i < a){
   
        int r = upper_bound(z.begin(), z.end(), z[i] + w - 1) - z.begin() - 1;
        segs.emplace_back(i, r);
        i = r + 1;
    }
    return segs.size();
}

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

    cin >> a >> b >> c;
    K = b + c;
    z.resize(a);
    for(int i = 0; i < a; i++) cin >> z[i];
    sort(z.begin(), z.end());

  
    int L = 1, R = z.back() - z.front() + 1, best = R;
    vector<pair<int,int>> best_segs, tmp;
    while(L <= R){
        int mid = (L + R) >> 1;
        int need = count_segments(mid, tmp);
        if(need <= K){
            best = mid;
            best_segs = tmp;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }

 
    while((int)best_segs.size() < K)
        best_segs.emplace_back(-1,-1);

    vector<int> lens(K);
    for(int i = 0; i < K; i++){
        auto [l,r] = best_segs[i];
        if(l == -1) lens[i] = 0;
        else        lens[i] = z[r] - z[l] + 1;
    }
   
    sort(lens.begin(), lens.end(), greater<int>());
    for(int i = 0; i < c; i++){
        int x = lens[i];
        lens[i] = (x + 1) / 2;
    }

    
    int answer = *max_element(lens.begin(), lens.end());
    cout << answer << "\n";
    return 0;
}

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