1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int maxPossibleScore(std::vector<int>& start, int d) {
        std::sort(start.begin(), start.end());
        int n = start.size();
        long long left = 0, right = (start.back() - start[0] + d) / (n - 1) + 1;
        
        while (right >= left) {
            long long mid = (left + right) / 2;
            long long prev = start[0];
            bool valid = true;
            for (int i = 1; i < n; ++i) {
                prev = std::max(prev + mid, (long long)start[i]);
                if (prev - start[i] > d) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        
        return right;
    }
};