Walls: Maximum Cubes in Adjacent Pyramids
Autumn Tournament (2024)
Submission name: walls.cpp
Problem summary
Reduce the heights of N consecutive positive towers to form adjacent walls. Each wall is an odd-length pyramid 1,2,...,h,...,2,1; height 1 is allowed. Maximize the total number of cubes retained. Towers cannot move and gaps cannot close.
Source clarification. The original second sample prints 18, but its own explanation describes a valid partition of area 19. Exhaustive small-instance checking confirms the recurrence. This page uses the consistent first sample and explicitly flags the source typo.
Input
Read N, then N tower heights.
Output
Print the maximum retained number of cubes.
Constraints
1 <= N <= 500000; 1 <= A[i] <= 10^9; 1.5 seconds; 512 MB.
Worked example
Original statement sample, using the documented local driver for grader tasks.
Input
7 3 1 4 2 5 9 2
Output
11
Solution analysis
- First compute H[i], the largest possible pyramid centered at i. A left pass limits heights by the preceding height plus one, and a symmetric right pass does the same from the other side. Because every height is positive, an optimum covers every position: a missing position can always become its own one-cube wall.
- Let dp[j] be the optimum for the first j towers. A final wall ending at zero-based i and starting at j has height h=(i-j+2)/2 and contributes h^2 cubes. It is valid exactly when j and i have equal parity and H[i-h+1]>=h. Shortening a valid wall while keeping its right endpoint produces a pyramid no higher than the previous one at any common position. Thus valid heights form an initial interval; binary-search its maximum.
- For x=i+2, expand the transition: 4*dp[i+1] = x^2 + max_j(-2*j*x + 4*dp[j] + j^2). Eligible starts j have one parity and lie in a suffix beginning at the smallest valid start. Use one reversed Fenwick tree per parity; every node stores an upper envelope of lines. This converts the suffix restriction into O(log N) hull operations.
- Both inserted slopes and query chronology are ordered: slopes decrease and x increases. In each hull, its last line is the current winner. If the preceding, steeper line overtakes it, discard the last line permanently. On insertion, discard a new line already dominated at the current x, since its smaller slope cannot recover later; remove geometrically redundant middle lines by exact cross-products. Every inserted copy is pushed and popped at most once.
- For the sample, H permits a height-3 pyramid over the last five towers. The partition [1][1][1,2,3,2,1] retains 1+1+9=11 cubes, better than the two height-2 pyramids retaining only 9.
Why it works
The two directional passes characterize exactly the feasible centered pyramids. Every optimal prefix ends with a valid wall, so the DP recurrence is exhaustive. Its algebraic transformation changes no values. Reversed Fenwick nodes partition exactly the eligible suffix, while the ordered convex hull retains every line that can win a future query. Hence each computed prefix optimum, and the final result, is correct.
Watch out. Use h^2, not h(h+1)/2, for pyramid area. Keep starts of different parity separate. Ordinary arbitrary-query hull logic is not interchangeable with the chronological future-winner stack. Towers cannot be shifted together after deletion.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct WallLine{
long long slope;
long long intercept;
long long value(long long x)const{
return slope*x+intercept;
}
};
struct FutureHull{
vector<WallLine>lines;
long long query(long long x){
// Once an older, steeper line wins, the newer line never wins again.
while(lines.size()>=2&&lines[lines.size()-2].value(x)>=lines.back().value(x)){
lines.pop_back();
}
return lines.empty()?-4000000000000000000LL:lines.back().value(x);
}
void add(WallLine current,long long x){
if(!lines.empty()&&query(x)>=current.value(x)){
return;
}
while(lines.size()>=2){
WallLine first=lines[lines.size()-2];
WallLine second=lines.back();
long long left=(second.intercept-first.intercept)*(second.slope-current.slope);
long long right=(current.intercept-second.intercept)*(first.slope-second.slope);
if(left>right){
break;
}
lines.pop_back();
}
lines.push_back(current);
}
};
struct SuffixHulls{
int capacity;
vector<FutureHull>tree;
explicit SuffixHulls(int size):capacity(size),tree(size+1){
}
void add(int position,WallLine line,long long x){
for(int index=capacity-position;index<=capacity;index+=index&-index){
tree[index].add(line,x);
}
}
long long query(int firstPosition,long long x){
long long answer=-4000000000000000000LL;
for(int index=capacity-firstPosition;index>0;index-=index&-index){
answer=max(answer,tree[index].query(x));
}
return answer;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>maximumHeight(n);
for(int&value:maximumHeight){
cin>>value;
}
for(int i=0;i<n;++i){
maximumHeight[i]=min(maximumHeight[i],i==0?1:maximumHeight[i-1]+1);
}
for(int i=n-1;i>=0;--i){
maximumHeight[i]=min(maximumHeight[i],i==n-1?1:maximumHeight[i+1]+1);
}
int capacity=n/2+2;
SuffixHulls even(capacity);
SuffixHulls odd(capacity);
even.add(0,{0,0},2);
long long answer=0;
for(int end=0;end<n;++end){
int low=1;
int high=(end+2)/2;
while(low<high){
int height=(low+high+1)/2;
int center=end-height+1;
if(maximumHeight[center]>=height){
low=height;
}
else{
high=height-1;
}
}
int firstStart=end-2*low+2;
long long x=end+2;
SuffixHulls¤t=end%2==0?even:odd;
answer=(x*x+current.query(firstStart/2,x))/4;
int nextStart=end+1;
WallLine nextLine={-2LL*nextStart,4*answer+1LL*nextStart*nextStart};
SuffixHulls&next=nextStart%2==0?even:odd;
next.add(nextStart/2,nextLine,x);
}
cout<<answer<<'\n';
}