# WA on 1 testcase- Lazy Cow (Silver prefix sums)

Here is the link to the problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=416.

I glanced at the first part of the editorial, and my solution uses the same approach. I rotate the grid 45 degrees clockwise and make the diagonals of the original grid the rows of my new grid (with 0s in between the numbers). Then, I take prefix sums and try all N^2 starting locations and their corresponding (2K+1)\times (2K+1) subarrays.

#include <bits/stdc++.h>

using namespace std;

const int MX = 400;

int n, k;
vector<vector<int>> grid;

int main()
{
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout);

cin >> n >> k;
grid.resize(2*n, vector<int>(2*n));

for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
int diag = i+j+1;
// convert to a diagonal grid, 0s in between elements
cin >> grid[diag][n-(diag-1)+2*j];
}
}

for(int i=1; i<2*n; ++i){
for(int j=1; j<2*n; ++j){
// take prefix sums
grid[i][j] += grid[i][j-1] + grid[i-1][j] - grid[i-1][j-1];
}
}

auto f = [&](int x){ // for bounding the indices
return max(min(x,2*n-1),1);
};

int mxSum = 0;
for(int i=0; i<2*n; ++i){
for(int j=0; j<2*n; ++j){
int bi = f(i+k), bj = f(j+k), // big i, big j
si = f(i-k-1), sj = f(j-k-1); // small i, small j
int lr = grid[bi][bj],
ur = grid[si][bj],
ll = grid[bi][sj],
ul = grid[si][sj];
mxSum = max(mxSum, lr - ll - ur + ul);
}
}

cout << mxSum << '\n';
}


This gives a WA on test case 9 even with the correct logic. However, after debugging a little bit, I found that this brute-force loop passes 10/10:

    for(int i=0; i<2*n; ++i){
for(int j=0; j<2*n; ++j){
int bi = f(i+2*k+1), bj = f(j+2*k+1), si = i, sj = j;
int lr = grid[bi][bj],
ur = grid[si][bj],
ll = grid[bi][sj],
ul = grid[si][sj];
mxSum = max(mxSum, lr - ll - ur + ul);
}
}


In my first code, I specify a starting location and sum the surrounding square of side length 2K+1. In the second code, I specify the top-left corner of the rectangle ((i+1,j+1)) and explicitly try all (2K+1)\times (2K+1) squares present in the grid.

By the word problem statement, it seems that the logic of my first code should work, but it doesn’t. Can you please explain why?