귀농

dp, partial sum

출처: BOJ 귀농

SOL)
무조건 전부 탐색을 하면 n^6정도의 시간복잡도가 나온다.
수익의 합이 최대 2500000이 안넘는 것을 이용한다.
정해진 위치에서 상근이가 만들 수 있는 총 수익 조합을 checked배열에
업데이를 해놓고 선영이가 만들 수 있는 수익에 checked값을 그냥 답에
더해준다. 즉, 만약 상근이가 만들 수 있었다면 알아서 답이 증가했을 것이다.

방향은 (왼쪽 위, 오르쪽 아래), (오른쪽 위, 왼쪽 아래) 경우가 나오는데
전자의 경우를 계산했다면 checked배열을 왼상태로 돌려놓고
후자의 경우를 계산해준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

const int mx = 50 * 50 * 1000;

int bot[100][100];
int psum[100][100];
int checked[2 * mx + 100];
int n;
int ans = 0;

void cal(int r, int c){
    //1
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][c] - psum[i - 1][c] - psum[r][j - 1] + psum[i - 1][j - 1];

            checked[val+mx]++;
        }
    }
    //1-2
    for (int i = r + 1; i <= n; i++){
        for (int j = c + 1; j <= n; j++){
            int val = psum[i][j] - psum[r][j] - psum[i][c] + psum[r][c];
            ans += checked[val+mx];
        }
    }
    //1-3
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][c] - psum[i - 1][c] - psum[r][j - 1] + psum[i - 1][j - 1];

            checked[val+mx]--;
        }
    }
    /////////////////////////////////

    //2-1
    for (int i = 1; i <= r; i++){
        for (int j = n; j >= c; j--){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][j] - psum[i - 1][j] - psum[r][c - 1] + psum[i - 1][c - 1];

            checked[val+mx]++;
        }
    }
    //2-2

    for (int i = r + 1; i <= n; i++){
        for (int j = c - 1; j >= 1; j--){
            int val = psum[i][c-1] - psum[i][j-1] - psum[r][c - 1] + psum[r][j-1];
            ans += checked[val+ mx];
        }
    }

    //2-3
    for (int i = 1; i <= r; i++){
        for (int j = n; j >= c; j--){
            int val;
            if (i == r && j == c)
                val= bot[i][j];
            else
                val = psum[r][j] - psum[i - 1][j] - psum[r][c - 1] + psum[i - 1][c - 1];

            checked[val+mx]--;
        }
    }

}

int main(){
    //freopen("input.txt", "r", stdin);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            scanf("%d", &bot[i][j]);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){

            for (int r = 1; r <= i; r++){
                for (int c = 1; c <= j; c++){
                    psum[i][j] += bot[r][c];
                }
            }
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){

            cal(i, j);
        }
    }

    printf("%d", ans);

    return 0;
}