升级蓄水池

import java.util.*;

public class Main{
    static int n = 0;
    static int m = 0;
    static int[] arr;
    static int maxHeight = 0;
    static int leftIndex = 0;
    static int rightIndex = 0;
    static int[] maxLeft;
    static int[] maxRight;
    static boolean[] canPut;//自己补充剪枝
    enum Type {LEFT, MID, RIGHT};
    
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        arr = new int[n];
        canPut = new boolean[n];
        maxHeight = 0;
        leftIndex = 0;
        rightIndex = 0;
        for(int i = 0; i < n; i++){
            arr[i] = input.nextInt();
            if(maxHeight < arr[i]){
                maxHeight = arr[i];
                leftIndex = i;
            }
            if(maxHeight == arr[i])
                rightIndex = i;
        }
        maxLeft = new int[n];
        maxRight = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++) {
            maxLeft[i] = max;
            max = Math.max(max, arr[i]);
        }
        max = 0;
        for(int i = n - 1; i >= 0; i--) {
            maxRight[i] = max;
            max = Math.max(max, arr[i]);
        }
        m = input.nextInt();
        System.out.println(getCapacity(arr) + solve());
    }
    public static int solve(){
        int maxArea = 0;
        int totalArea = 0;
        //前
        for(int i = 0; i < leftIndex; i++){
            if(!canPut[i]) {
                continue;
            }
            int less = Math.min(maxHeight - arr[i], m);
            totalArea = 0;
            totalArea += addHeightAtIndex(arr, i, less);//尝试加满高
            if(less != m){//arr[i],leftIndex撤销
                arr[i] += less;
                int temp = leftIndex;
                leftIndex = i;
                totalArea += Math.max(countRemnant(arr, Type.LEFT, m - less), 
                                        Math.max(countRemnant(arr, Type.MID, m - less),
                                             countRemnant(arr, Type.RIGHT, m - less))); //中或后
                leftIndex = temp;
                arr[i] -= less;
            }
            maxArea = Math.max(maxArea,totalArea);
        }
        //后
        for(int i = n - 1; i > rightIndex; i--){
            if(!canPut[i]) {
                continue;
            }
            int tmp = Math.min(maxHeight - arr[i], m);
            totalArea = 0;
            totalArea += addHeightAtIndex(arr, i, tmp);
            if(tmp != m){
                arr[i] += tmp;
                int temp = rightIndex;
                rightIndex = i;
                totalArea += Math.max (countRemnant(arr, Type.LEFT, m - tmp),
                                     Math.max(countRemnant(arr, Type.MID, m - tmp),
                                         countRemnant(arr, Type.RIGHT, m - tmp))); //中或前
                rightIndex = temp;
                arr[i] -= tmp;
            }
            maxArea = Math.max(maxArea,totalArea);
        }
        //中
        if(leftIndex != rightIndex) maxArea = Math.max(maxArea, countRemnant(arr, Type.MID, m)); //中
        return maxArea;
    }
     
    public static int countRemnant(int[] arr, Type type, int tempM){
        int maxArea = 0;
        int totArea = 0;
        if(type == Type.LEFT || type == Type.RIGHT){ //前后
            int st = type == Type.RIGHT ? rightIndex + 1 : 0;
            int en = type == Type.RIGHT ? n : leftIndex;
            for(int i = st; i < en; i++){
                if(!canPut[i]) {
                    continue;
                }
                totArea = 0;
                int less = Math.min(maxHeight - arr[i], tempM);
                totArea += addHeightAtIndex(arr, i, less);
                if(less != tempM){
                    arr[i] += less; 
                    int temp = 0;
                    if(type == Type.LEFT) {
                        temp = leftIndex;
                        leftIndex = i;
                    }else {
                        temp = rightIndex;
                        rightIndex = i;
                    }
                    totArea += countRemnant(arr, Type.MID, tempM - less);
                    
                    if(type == Type.LEFT) 
                        leftIndex = temp;
                    else 
                        rightIndex = temp;
                    arr[i] -= less;
                }
                maxArea = Math.max(maxArea, totArea);
            }
        }
        else{ //中
            int tmp1 = tempM / 2;
            if(tmp1 == 0 && leftIndex == 0 && rightIndex == n - 1){
                return 0;
            }
            totArea = (rightIndex - leftIndex - 1) * tmp1;
            arr[leftIndex] += tmp1;
            arr[rightIndex] += tmp1;
            maxHeight += tmp1;
            if(tmp1 * 2 == tempM - 1) {//中间后剩下的两边都可能
                totArea += Math.max(countRemnant(arr, Type.LEFT, 1), countRemnant(arr, Type.RIGHT, 1));
            }
            
            arr[rightIndex] -= tmp1;
            arr[leftIndex] -= tmp1;
            maxHeight -= tmp1;
            maxArea = Math.max(maxArea, totArea);
        }
        return maxArea;
    }
     
    public static int addHeightAtIndex(int[] arr, int index, int change){
        int max = arr[index];
        int tot = 0;
        int sum = arr[index] + change;
        if(index < leftIndex){
            max = Math.max(max, maxLeft[index]);
            for(int i = index + 1; i < leftIndex && arr[i] <= sum; i++){
                max = Math.max(arr[i], max);
                tot += sum > max ? (sum - max) : 0;
            }
        }
        else if(index > rightIndex){
            max = Math.max(max, maxRight[index]);
            for(int i = index - 1; i > rightIndex && arr[i] <= sum; i--){
                max = Math.max(arr[i], max);
                tot += sum > max ? (sum - max) : 0;
            }
        }
        return tot;
    }
     
    public static int getCapacity(int[] arr){//现有能盛多少水
        int area = 0;
        int i = 0, j = arr.length - 1;
        int l = arr[i], r = arr[j];
        canPut[i] = true;
        canPut[j] = true;
        while(i < j){
            if(l > r){//由低到高
                area += r - arr[j];
                j--;
                if(arr[j] > r) {
                    canPut[j] = true;
                }
                r = Math.max(r, arr[j]);
            }
            else{
                area += l - arr[i];
                i++;
                if(arr[i] > l){
                    canPut[i] = true;
                }
                l = Math.max(l, arr[i]);
            }
        }
        return area;
    }
}