Description

Submission

class Solution {
    long count(long h, long n, long index) {
        long sum = 0;

        if(index+1 >= h) {
            sum += (h+1)*h/2;
            sum += index + 1 - h;
        } else {
            sum += (h + (h - index)) * (index + 1) / 2;
        }

        if(n - index >= h) {
            sum += (h+1)*h/2;
            sum += n - index - h;
        } else {
            sum += ((h - (n - index) + 1) + h) * (n - index) / 2;
        }

        return sum - h;
    }
public:
    int maxValue(int n, int index, int maxSum) {
        int l = 0, r = maxSum;

        while(l < r) {
            int mid = r - (r - l) / 2;
            if(count(mid, n, index) > (long)maxSum) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }

        return l;
    }
};