Proficient.
Put your skills to the test.

Problem summary

Given a nonnegative N×N table and threshold K, find the smallest side length M such that every axis-aligned M×M square of cells has sum at least K. Print−1 if no side length works.

Source clarification. The O(N²) monotone-frame idea is described in the official analysis: https://infos.infosbg.com/files/Contests/ETI/2019/B/analyses/B6_field_analysis.txt

Constraints

1 ≤ N ≤ 5000; 0 ≤ cell values ≤50; 1 ≤ K ≤2·10^9.

Worked example

Original statement sample.

5 10
1 2 3 4 5
10 0 7 0 4
0 0 2 1 3
5 0 3 0 2
0 5 0 8 0

3

Solution analysis

1. A 2D prefix table answers any square-sum query in O(1). Its entries fit in int: the full sum is at most5000²·50=1,250,000,000. Build each row with a running row sum to avoid a large intermediate addition of two overlapping prefix totals.
2. Scan all possible top-left corners while maintaining one globally nondecreasing candidate side, initially1. At a corner where the candidate square fits but has sum<K, increase its side and test again. Smaller side lengths have now been disproved globally. If the enlarged square leaves the board, that corner is simply irrelevant for this and all larger sides.
3. Previous successful corners need no retesting: enlarging a square keeps all of its old cells and only adds nonnegative values. Moreover the set of legal corners shrinks as side length grows. Thus after all corners are processed, every fitting square of the final side meets K. In the sample, a1×1 square with value2 and a2×2 square with sum9 rule out sides1 and2; side3 works everywhere.

Why it works

Each failed square proves that its side length is globally invalid, so the candidate never exceeds the true minimum without justification. Every earlier successful square remains successful if enlarged, by nonnegativity; corners that no longer fit disappear from the requirement. At the end all remaining fitting corners are certified, proving minimality. If side becomes N+1, even the full table failed, so no answer exists.

Watch out. The quantifier is every square, not at least one. The monotonic argument requires nonnegative cells. Skip out-of-board candidate squares rather than declaring failure at a boundary corner. Prefix indices need a zero border.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,target;
    cin>>n>>target;
    int stride=n+1;
    vector<int>prefix(static_cast<size_t>(stride)*stride,0);
    for(int row=1;row<=n;++row){
        int rowSum=0;
        for(int column=1;column<=n;++column){
            int value;
            cin>>value;
            rowSum+=value;
            prefix[static_cast<size_t>(row)*stride+column]=
                prefix[static_cast<size_t>(row-1)*stride+column]+rowSum;
        }
    }
    auto squareSum=[&](int row,int column,int side){
        int bottom=row+side-1;
        int right=column+side-1;
        return prefix[static_cast<size_t>(bottom)*stride+right]-
            prefix[static_cast<size_t>(row-1)*stride+right]-
            prefix[static_cast<size_t>(bottom)*stride+column-1]+
            prefix[static_cast<size_t>(row-1)*stride+column-1];
    };
    int side=1;
    for(int row=1;row<=n;++row){
        for(int column=1;column<=n;++column){
            // A failed size is globally impossible; the candidate only grows.
            while(row+side-1<=n&&column+side-1<=n&&squareSum(row,column,side)<target){
                ++side;
            }
        }
    }
    cout<<(side>n?-1:side)<<'\n';
}