vector> prefSum; vector> sufSum; int n,m; int getPrefixSum(int row, int left){ if(left==0) return 0; return prefSum[row][left-1]; } int getSuffixSum(int row, int right){ if(right==0) return 0; return sufSum[row][right-1]; } int solve(int row,int k, vector>& matrix){ if(k==0) return 0; if(row == n) return -1e9; int ans = -1; for(int i=0;i<=min(m,k);i++){ for(int j=0;j<=i;j++){ int left = j; int right = i-j; ans = max(ans, getPrefixSum(row,left) + getSuffixSum(row,right) + solve(row + 1, k - i,matrix)); } } return ans; } int getMaximumSum(vector> matrix, int k) { n = matrix.size(); m = matrix[0].size(); prefSum.resize(n, vector(m,0)); sufSum.resize(n, vector(m,0)); for(int i=0;i=0;j--){ if(j==m-1){ sufSum[i][j] = matrix[i][j]; } else{ sufSum[i][j] = sufSum[i][j+1] + matrix[i][j]; } } reverse(sufSum[i].begin(),sufSum[i].end()); } return solve(0,k,matrix); }