Real problems.
Your next challenge.

Problem summary

Zero-thickness partitions stand one centimetre apart across a box of width one. Selected partitions may be raised by up to their given allowance. Maximize retained water volume, and among maximum-volume arrangements minimize how many partitions are raised.

Constraints

1<N<1000000; 0<K≤N; original heights and increases are positive integers below 1000000.

Worked example

Original statement sample.

6
2 4 2 4 2 1
2
2 1
4 1

1 14

Solution analysis

1. For the gap after partition i, water depth is the smaller of the highest partition on its left and the highest on its right. Partitions have zero thickness, so do not subtract their heights as in the usual solid-bar rainwater problem. Raising partitions never decreases this volume; therefore using every full allowance gives the maximum possible volume, computed with prefix and suffix maxima.
2. Let C be the second-largest possible partition height, counting equal values separately. No gap can have water above C, so cap all possible heights at C. At least two partitions now attain C. Between the first and last such positions, level C is attainable. Before the first, each gap’s target is the running possible-height maximum; after the last, use the symmetric right-to-left maximum.
3. Scan the left part, keeping the maximum height actually available from original heights and already forced raises. Whenever it falls short of the target, the current partition is a new possible-height record and is the only partition seen so far capable of reaching that target: raising it is forced. Scan the right part symmetrically. These regions are disjoint. Interior partitions need no changes.
4. In the sample the maximum gap depths are 2,4,4,3,1, totaling 14. Both height-4 partitions already exist. On the right scan, raising partition 4 from 2 to 3 is forced; raising partition 2 would not improve any gap. Thus the minimum count is one.

Why it works

Capping at the second-largest possible height preserves every gap’s optimum because a water level needs supporting partitions on two sides. On the left outer region, the target is its prefix maximum, since a capped height-C partition remains on the right. A target not reached by original heights and prior required raises can first be reached only at the current strict possible-height record, so that raise is necessary. Performing it suffices until the next record. The symmetric proof applies on the right; the two capped peaks then support all intervening gaps. The resulting necessary raises attain all optimal gap depths, proving both maximal volume and minimal count.

Watch out. Do not subtract partition heights from gap depths: these are thin walls, not unit-width solid bars. Indices in the input are 0-based. The second-largest height includes multiplicity, so two equal maxima give that same cap.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>original(n);
    for(int&height:original){
        cin>>height;
    }
    vector<int>possible=original;
    int changes;
    cin>>changes;
    for(int change=0;change<changes;change++){
        int index;
        int increase;
        cin>>index>>increase;
        possible[index]=original[index]+increase;
    }
    int largest=0;
    int cap=0;
    for(int height:possible){
        if(height>=largest){
            cap=largest;
            largest=height;
        }
        else{
            cap=max(cap,height);
        }
    }
    vector<int>suffix(n);
    suffix[n-1]=possible[n-1];
    for(int i=n-2;i>=0;i--){
        suffix[i]=max(possible[i],suffix[i+1]);
    }
    long long volume=0;
    int prefix=0;
    for(int i=0;i+1<n;i++){
        prefix=max(prefix,possible[i]);
        volume+=min(prefix,suffix[i+1]);
    }
    int firstPeak=0;
    while(possible[firstPeak]<cap){
        firstPeak++;
    }
    int lastPeak=n-1;
    while(possible[lastPeak]<cap){
        lastPeak--;
    }
    int raised=0;
    int actual=0;
    int target=0;
    for(int i=0;i<=firstPeak;i++){
        actual=max(actual,original[i]);
        target=max(target,min(possible[i],cap));
        if(actual<target){
            // A new required record can only be reached at this partition.
            raised++;
            actual=target;
        }
    }
    actual=0;
    target=0;
    for(int i=n-1;i>=lastPeak;i--){
        actual=max(actual,original[i]);
        target=max(target,min(possible[i],cap));
        if(actual<target){
            raised++;
            actual=target;
        }
    }
    cout<<raised<<' '<<volume<<'\n';
}