Proficient.
Put your skills to the test.

Problem summary

Partitions of zero thickness stand one centimeter apart. Some may be raised by specified integer allowances. First maximize the water volume in the gaps, then minimize how many partitions must be raised to achieve that maximum. The box width is one centimeter.

Source clarification. The same partition-water problem also appears in Arena’s Group C archive. This page preserves the Group B Autumn source identity. The full linear record-based solution follows https://infos.infosbg.com/files/Contests/ETI/2019/B/analyses/B5_rain_analysis.docx

Constraints

1 < N <1000000; 0 < K ≤N; original heights and allowed increases are positive and below1000000.

Worked example

Original statement sample.

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

1 14

Solution analysis

1. Apply every allowed increase conceptually. This cannot reduce water, so it determines the maximum target volume. The gap after i fills to min(maximum height through i, maximum height after i). Unlike the common solid-bar version, no partition height is subtracted: each partition has zero thickness and the water occupies the N−1 gaps.
2. Cap possible partition heights at C, their second-largest height counting equal values. No gap can hold water above C because water needs support on two sides. There are now at least two peaks of height C. Between the first and last, no interior partition needs raising. The outer left region must realize its successive prefix-record heights, and the outer right region its suffix records.
3. Scan each outer region from its boundary. Keep the greatest original height or height already forced by a previous raise, and the required possible-height record. If the available maximum is too small, the current new record is the only partition that can supply the missing support at that point: raising it is unavoidable. Count these forced raises, applying only as much increase as necessary.
4. For2,4,2,4,2,1 with increases at positions2 and4, the target gap depths are2,4,4,3,1, totaling14. Existing height4 peaks already support the middle. Only position4 must rise from2 to3; raising position2 adds no water. Hence output1 14.

Why it works

Maximal possible heights establish an upper bound achieved by using all allowances. Capping at the second-largest height preserves that bound for every gap. In each outer region, every target prefix/suffix record not already supplied by an original height is first attainable only at its own record partition, making that raise necessary. Those raises also suffice to realize all target gap levels; the two capped peaks support the entire middle. Thus the construction attains maximum volume with minimum raised count.

Watch out. Do not subtract heights as though partitions were solid bars. Count equal maximum heights separately when finding the second-largest. Input partition indices are0-based. Some allowances are unnecessary and must not be counted.

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';
}