Submission #58665308

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef modint998244353 mi;

ll a[100005];

int main(){
    ll n,l;cin>>n>>l;
    int k;cin>>k;
    rep(i,n)cin>>a[i];
    a[n]=l;
    n++;

    ll lb=-1,ub=1e15;
    while(ub-lb>1){
        ll mi=(ub+lb)/2;
        int cnt=0;
        ll last=0;
        rep(i,n){
            if(a[i]-last>=mi){
                cnt++;
                last=a[i];
            }
        }
        if(cnt>k)lb=mi;
        else ub=mi;
    }
    cout<<lb<<endl;
}

Submission Info

Submission Time
Task 001 - Yokan Party（★4）
User Rho17
Language C++ 20 (gcc 12.2)
Score 4
Code Size 685 Byte
Status AC
Exec Time 32 ms
Memory 4420 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 4 / 4
Status
AC × 5
AC × 29
Set Name Test Cases
Sample 01_01_sample_picture_01.txt, 01_02_sample_01.txt, 01_02_sample_02.txt, 01_02_sample_03.txt, 01_02_sample_04.txt
All 01_01_sample_picture_01.txt, 01_02_sample_01.txt, 01_02_sample_02.txt, 01_02_sample_03.txt, 01_02_sample_04.txt, 02_fixed_01.txt, 02_fixed_02.txt, 02_fixed_03.txt, 03_k_sensitive_01.txt, 03_k_sensitive_02.txt, 03_k_sensitive_03.txt, 03_k_sensitive_04.txt, 04_random_small_01.txt, 04_random_small_02.txt, 04_random_small_03.txt, 05_random_bias_01.txt, 05_random_bias_02.txt, 05_random_bias_03.txt, 06_random_01.txt, 06_random_02.txt, 06_random_03.txt, 06_random_04.txt, 07_random_max_01.txt, 07_random_max_02.txt, 07_random_max_03.txt, 07_random_max_04.txt, 08_equally_01.txt, 08_equally_02.txt, 09_max_01.txt
Case Name Status Exec Time Memory
01_01_sample_picture_01.txt AC 1 ms 3500 KiB
01_02_sample_01.txt AC 1 ms 3644 KiB
01_02_sample_02.txt AC 1 ms 3524 KiB
01_02_sample_03.txt AC 1 ms 3568 KiB
01_02_sample_04.txt AC 1 ms 3708 KiB
02_fixed_01.txt AC 1 ms 3580 KiB
02_fixed_02.txt AC 19 ms 4352 KiB
02_fixed_03.txt AC 29 ms 4352 KiB
03_k_sensitive_01.txt AC 1 ms 3508 KiB
03_k_sensitive_02.txt AC 1 ms 3508 KiB
03_k_sensitive_03.txt AC 1 ms 3476 KiB
03_k_sensitive_04.txt AC 1 ms 3556 KiB
04_random_small_01.txt AC 1 ms 3564 KiB
04_random_small_02.txt AC 1 ms 3504 KiB
04_random_small_03.txt AC 1 ms 3564 KiB
05_random_bias_01.txt AC 21 ms 4332 KiB
05_random_bias_02.txt AC 28 ms 4224 KiB
05_random_bias_03.txt AC 28 ms 4304 KiB
06_random_01.txt AC 27 ms 4200 KiB
06_random_02.txt AC 22 ms 4268 KiB
06_random_03.txt AC 28 ms 4332 KiB
06_random_04.txt AC 30 ms 4288 KiB
07_random_max_01.txt AC 27 ms 4420 KiB
07_random_max_02.txt AC 32 ms 4304 KiB
07_random_max_03.txt AC 29 ms 4352 KiB
07_random_max_04.txt AC 31 ms 4284 KiB
08_equally_01.txt AC 27 ms 4352 KiB
08_equally_02.txt AC 19 ms 4352 KiB
09_max_01.txt AC 28 ms 4304 KiB