Submission

Score: 0

User: a0ms1n

Problemset: Abacus

Language: cpp

Time: 0.717 second

Submitted On: 2025-04-23 00:29:08

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,k;
int arr[(int)2e3+1];

int area(int x){
    if(x<=0)return 0;
    if(x&1)return ((x+1)*(x+1))/4;
    else return ((x/2)*(x/2+1));
}

bool cando(int t){
    int sum = 0;
    for(int i=0;i<n;i++){
        sum += area(2*t+1);
        if(i==n-1)continue;
        int di = arr[i]+t;
        int dj = arr[i+1]-t;
        if(di<dj)continue;
        sum -= area(di-dj+1);
    }
    return sum>=k;
}

signed main(){
    cin>>n>>k;
    
    for(int i=0;i<n;i++)cin>>arr[i];
    sort(arr,arr+n);
    int l=0,r=min(k,(int)1e9);
    for(int b=r/2;b>0;b>>=1ll){
        while(r-b>=l && cando(r-b))r-=b;
    }
    cout<<r;


    return 0;
}