2512 예산 (PS)

#include <stdio.h>
 
int arr[10000] = { 0 };
 
int main() {
    int n,lim,st=0,max=0;
    scanf("%d", &n);
    getchar();
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        st += arr[i];
        
        if (arr[i] > max)
            max = arr[i];
    }
    scanf("%d", &lim);
    getchar();
 
    if (lim >= st) {
        printf("%d", max);
        return 0;
    }
 
    int low = 0, high = 1000000000;
    while (low + 1 < high) {
        int mid = (low + high) / 2;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (mid > arr[i])
                sum += arr[i];
            else
                sum += mid;
        }
 
        if (sum > lim)
            high = mid;
        else
            low = mid;
    }
    printf("%d", low);
}