2D range sum in O(n^3)

11951.cpp

#include <numeric>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int T,N,M,K;
int strip[128][128];

//       s     k
//   |-+-+-+-+-+
//   |   |     |
// i +-+-+-+-+-+
//   |   |#####|  <--- sum   
// j +-+-+-+-+-+


int main(){
	scanf("%d", &T);
	N=M=K=0;
	for(int t=0;t<T;++t){
		memset(strip, 0, sizeof(strip));
		scanf("%d %d %d", &N, &M, &K);
		for(int i=0;i<N;++i){
			for(int j=0;j<M;++j){
				scanf("%d", &strip[i][j]);
				// row sum: sum of elem above it
				if(i>0) strip[i][j]+=strip[i-1][j];
			}
		}
		
		int min_cost=numeric_limits<int>::max(), column_sum, max_area=0;
		for(int i=0;i<N;++i){ //start row
			for(int j=i;j<N;++j){ //end row
					int start = 0, area = 0, cost=0;
					for(int k=0;k<M;++k){
						column_sum = strip[j][k];
						if(i>0) column_sum -= strip[i-1][k];
						cost += column_sum;
						if(cost>K){ 
							while(cost>K){
								cost -= strip[j][start];
								// row sum: so we have to add it back
								if(i>0) cost += strip[i-1][start]; 
								start++;
							}
						}	
						area = (k-start+1)*(j-i+1);
						if(area>max_area || (area==max_area && cost<min_cost)){
							max_area=area; 
							min_cost=cost;
						}
					}
				
			}
		}
		//check min_cost is still max case
		printf("Case #%d: %d %d\n", t+1, max_area, min_cost==numeric_limits<int>::max()?0:min_cost);
	}
	return 0;
}