Largest Rectangle in a Tiled Matrix
National Olympiad — Municipal round (2026 season)
Submission name: matrix.cpp
Problem summary
Tile an N×M binary matrix R times vertically and C times horizontally. Find the largest all-one axis-aligned rectangle in the resulting matrix.
Input
N M R C, followed by N binary strings of length M.
Output
The maximum rectangle area.
Constraints
1 ≤ N,M ≤ 2000; 1 ≤ R,C ≤ 1000000.
Worked example
Official statement example.
Input
3 4 2 3 0110 1111 0101
Output
12
Solution analysis
- A vertical run in a column containing a zero has length less than N; two vertical copies suffice to expose any run crossing a tile boundary. A column containing only ones instead permits the full height N·R. Scan min(R,2) copies of the rows, maintaining histogram heights, but give these all-one columns their full final height.
- At each row compute the largest histogram rectangle with a monotone stack over min(C,2) horizontal copies. If a popped rectangle spans at least M columns, every base-column residue supports its height, so its width can expand to the full M·C. Otherwise its ordinary span is already the maximum possible bounded width.
- A rectangle bounded in height and width is represented in the doubled scan. An unbounded dimension is replaced by the true tiled dimension. In the official example the all-one second row expands across all 12 tiled columns, giving area 12. Heights and widths may each reach 2·10⁹, so use 64-bit areas.
Why it works
For any fixed set of columns, either some column contains a zero in one vertical period, in which case every valid common vertical run has length less than N and occurs within two row copies, or all those columns are all-one and full height NR is achievable. Thus the modified histograms represent all possible optimal heights. For a histogram threshold, a horizontal run shorter than M is fully exposed by two copies; a run of at least M covers all column residues and extends to the whole tiled width. The monotone-stack algorithm evaluates the maximal span for every limiting height. Every expanded candidate is feasible by periodicity, and every optimal rectangle appears among these candidates, proving exactness.
Watch out. Do not build the huge tiled matrix. One-copy inputs must not wrap across boundaries. All-one columns and full-period horizontal runs require expansion to the true dimensions.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: For any fixed set of columns, either some column contains a zero in one vertical period,
// in which case every valid common vertical run has length less than N and occurs within two row
// copies, or all those columns are all-one and full height NR is achievable. Thus the modified
// histograms represent all possible optimal heights.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
long long r,c;
cin>>n>>m>>r>>c;
vector<string>a(n);
vector<int>full(m,1);
for(string&row:a){
cin>>row;
for(int j=0;j<m;++j){
if(row[j]=='0'){
full[j]=0;
}
}
}
int rows=n*static_cast<int>(min(2LL,r));
int columns=m*static_cast<int>(min(2LL,c));
vector<long long>height(columns);
vector<int>stack;
stack.reserve(columns);
long long answer=0;
for(int i=0;i<rows;++i){
for(int j=0;j<columns;++j){
int base=j%m;
if(full[base]){
height[j]=n*r;
}
else if(a[i%n][base]=='1'){
++height[j];
}
else{
height[j]=0;
}
}
stack.clear();
for(int j=0;j<=columns;++j){
long long current=j==columns?-1:height[j];
while(!stack.empty()&&height[stack.back()]>=current){
long long h=height[stack.back()];
stack.pop_back();
int left=stack.empty()?-1:stack.back();
long long width=j-left-1;
if(width>=m){
width=m*c;
}
answer=max(answer,h*width);
}
if(j<columns){
stack.push_back(j);
}
}
}
cout<<answer<<'\n';
}