leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1802.cpp (565B)

      1 class Solution {
      2   public:
      3     int maxValue(int n, int index, int maxSum) {
      4         const int a = index, b = n - index - 1;
      5         int low = 0, high = maxSum;
      6 
      7         const auto arit = [](long n, int mid) { return (long)n * mid - n * (n + 1) / 2; };
      8         while (low < high) {
      9             int mid = (low + high + 1) / 2;
     10             long res = mid + arit(min(a, mid - 1), mid) + arit(min(b, mid - 1), mid);
     11             if (res <= maxSum - n)
     12                 low = mid;
     13             else
     14                 high = mid - 1;
     15         }
     16         return low + 1;
     17     }
     18 };