题解：AT_abc395_f [ABC395F] Smooth Occlusion

#include<bits/stdc++.h>
using namespace std;
#define bit(x) (x&-x)
#define rep(l,r,i) for(int i=l;i<=r;i++)
#define per(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
#define int long long 
int N;
int X;
vector<int> U, D;
vector<int> sum_UD;
bool is_feasible(int H) {
    int curr_low = max(H - D[0], 0LL);
    int curr_high = min(U[0], H);
    if (curr_low > curr_high) return false;
    rep(1,N-1,i) {
        int a = max(H-D[i], 0LL);
        int b = min(U[i],H);
        int new_low = max(a,curr_low-X);
        int new_high = min(b,curr_high+X);
        if (new_low > new_high) return false;
        curr_low = new_low;
        curr_high = new_high;
    }
    return true;
}
signed main() {
    cin>>N>>X;
    U.resize(N);
    D.resize(N);
    sum_UD.resize(N);
    int H_max = LONG_LONG_MAX;
    rep(0,N-1,i) {
        cin>>U[i]>>D[i];
        sum_UD[i] = U[i] + D[i];
        if (sum_UD[i] < H_max)
            H_max = sum_UD[i];
    }
    int left = 0, right = H_max;
    int best_H = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (is_feasible(mid)) {
            best_H = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    int total_sum = 0;
    for (int s:sum_UD) {
        total_sum += s;
    }
    int cost = total_sum - best_H * N;
    cout<<cost;
    return 0;
}