leetcode

commit 07e2b532294e6b2ae9d493c79c5cac43dd05efc5
parent 541fb16da7ff5184ebf405b0bc9fa3abf617c24e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 10 Jun 2023 18:58:49 +0200

Daily Problem

Diffstat:
A
Problems/1802.cpp
 | 
20
++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 21 insertions(+), 0 deletions(-)
diff --git a/Problems/1802.cpp b/Problems/1802.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+  int maxValue(int n, int index, int maxSum) {
+    const int a = index, b = n - index - 1;
+    int low = 0, high = maxSum;
+
+    const auto arit = [](long n, int mid) {
+      return (long)n * mid - n * (n + 1) / 2;
+    };
+    while (low < high) {
+      int mid = (low + high + 1) / 2;
+      long res = mid + arit(min(a, mid - 1), mid) + arit(min(b, mid - 1), mid);
+      if (res <= maxSum - n)
+        low = mid;
+      else
+        high = mid - 1;
+    }
+    return low + 1;
+  }
+};
diff --git a/README.md b/README.md
@@ -501,6 +501,7 @@ for solving problems.
 |  1786  |   Medium   | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp)                          |
 |  1791  |    Easy    | [Find Center of Star Graph](Problems/1791.cpp)                                                   |
 |  1799  |   Medium   | [Maximize Score After N Operations](Problems/1799.cpp)                                           |
+|  1802  |   Medium   | [Maximum Value at a Given Index in a Bounded Array](Problems/1802.cpp)                           |
 |  1822  |    Easy    | [Sign of the Product of an Array](Problems/1822.cpp)                                             |
 |  1823  |   Medium   | [Find the Winner of the Circular Game](Problems/1823.cpp)                                        |
 |  1833  |   Medium   | [Maximum Ice Cream Bars](Problems/1833.cpp)                                                      |