#1157466 (C++17) No.3513 Greedy Yokan Party

• 問題: No.3513 Greedy Yokan Party
• ユーザー: Yoyoyo8128
• 提出日時: 2026-04-16 09:23:08
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 390 ms / 2,000 ms
• コード長: 3,170 bytes
• コンパイル時間: 1,900 ms
• コンパイル使用メモリ: 216,216 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-24 20:53:54
• 合計ジャッジ時間: 13,436 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	AC * 1
other	AC * 26

ソースコード

#pragma region Yoyoyo

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using i128t=__int128_t;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const string Yes="Yes";
const string No="No";
const long long inf=1ll<<60;

#ifndef LOCAL
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr);
#define print(s) cout<<s<<endl;

template<typename T>
inline bool chmax(T &a,T b){return ((a<b)?(a=b,true):(false));}
template<typename T>
inline bool chmin(T &a,T b){return ((a>b)?(a=b,true):(false));}
template<typename T>
ll sum(const T&a){return accumulate(all(a),0LL);}

template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U>&p){
    os<<p.first<<" "<<p.second;
    return os;
}

template<typename T,typename U>
istream &operator>>(istream &is,pair<T,U>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<(i?" ":"")<<v[i];
    }
    return os;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(auto &x:v){
        is>>x;
    }
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<T>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<v[i]<<endl;
    }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<vector<T>>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<"i = "<<i<<endl;
        os<<v[i];
    }
    return os;
}

#ifdef LOCAL
template<class... Args>
void debug_out(Args... args){
    int _i=0;
    ((cerr<<(_i++?", ":" ")<<args), ...);
    cerr<<"\n";
}
#define debug(...){\
    cerr<<"["<<#__VA_ARGS__<<"]:";\
    debug_out(__VA_ARGS__);\
}
#else
#define debug(...)
#endif

#pragma endregion Yoyoyo



int main(){
    faster;
    ll N,L,K;
    cin>>N>>L>>K;
    ll sm=N-K+2;
    //2ピースの合計は、sm、N+1ピースあって、(K+1-2)個は長さ1
    ll ok=0,ng=L/2+1;
    vector<ll>A(N+2);
    for(int i=1;i<=N;i++)cin>>A[i];
    A[0]=0;A[N+1]=L;
    auto check = [&](ll md)->bool {
        ll now=inf;
        for(ll i=0;i<N+2;i++){
            if(A[i]>=md){
                ll dis=upper_bound(all(A),A[i]-md)-A.begin();
                dis--;
                chmin(now,i-dis);
            }
            if(A[i]+md<=L){
                ll dis=lower_bound(all(A),A[i]+md)-A.begin();
                if((dis-i)+now<=sm){
                    return true;
                }
            }
        }
        return false;
    };
    while(ng-ok>1){
        ll md=(ng+ok)/2;
        if(check(md)) ok=md;
        else ng=md;
    }
    cout<<ok<<"\n";
    {
        assert(1<=K && K<=N && N<=200000);
        assert(L<=1000000000);
        for(int i=0;i<N+1;i++){
            assert(0<=A[i] && A[i]<=L);
            assert(A[i]<A[i+1]);
        }
    }
}