February 2021 USACO Silver Problem 3

#1

Link to the problem

I was trying to solve this problem via an approach from someone on LC. However, I received 8/10 test cases (to be specific, the last two test cases…), and I wanted to know if anyone knew why this solution didn’t AC.

Here is my code:

#include <bits/stdc++.h>

using namespace std;

bool green_enough[501][501];
bool too_green[501][501];

int main(){
    int n; cin >> n;
    int g[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> g[i][j];
        }
    }
    bool green_enough[n][n];
    bool too_green[n][n];
    memset(green_enough, 0, sizeof(green_enough));
    memset(too_green, 0, sizeof(too_green));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            green_enough[i][j] = (g[i][j] >= 100);
            too_green[i][j] = (g[i][j] > 100);
        }
    }
    int dp1[n][n], dp2[n][n];
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == 0){
                dp1[i][j] = (green_enough[i][j] == 0 ? 0: 1);
            } else {
                dp1[i][j] = ((green_enough[i][j] == 0) ? 0: dp1[i-1][j] + 1);
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == 0){
                dp2[i][j] = (too_green[i][j] == 0 ? 0: 1);
            } else {
                dp2[i][j] = ((too_green[i][j] == 0) ? 0: dp2[i-1][j] + 1);
            }
        }
    }

    int res1 = 0, res2 = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int m = dp1[i][j];
            for(int k=j; k >= 0 && dp1[i][k] != 0; --k){
                m = min(m, dp1[i][k]);
                res1 += m;
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int m = dp2[i][j];
            for(int k=j; k >= 0 && dp2[i][k] != 0; --k){
                m = min(m, dp2[i][k]);
                res2 += m;
            }
        }
    }
    cout << res1 - res2 << endl;
}

Let me know what I did wrong. Thanks.

#2

You should reread the output format.

#3

Do you mean change the int to long long?

#4

Well, you can try it yourself.

1 Like
#5

Yay! Thanks for the help LOL. That was actually the problem smh. I should just conventionally stick to long long from now on :frowning:.