# [Gold III] 임스의 땅따먹기 [문제 링크](https://www.acmicpc.net/problem/33561) ## 문제 설명 <p>임스는 $N \times N$ 크기의 격자판 모양의 국가에서 살고 있다. 격자판의 $i$행 $j$열에 위치한 칸에는 해당 칸의 가치를 나타내는 음이 아닌 정수 $w_{ij}$가 적혀 있다.</p> <p>임스는 가지고 있는 땅의 일부분을 자신의 영역으로 정복하려고 한다. 임스가 정복하려고 하는 영역은 다음 조건을 만족해야 한다.</p> <ul> <li>임스의 영역은 각 변이 격자판과 평행한 <strong>정사각형 </strong>영역이다. 구체적으로 영역은 $1 \leq a \leq b \leq N, 1 \leq c \leq d \leq N, b - a = d - c$를 만족하는 정수 $(a, b, c, d)$에 대하여 다음과 같이 정의한다. <ul> <li>$a \leq x \leq b, c \leq y \leq d$를 만족하는 정수 $x, y$에 대해 $x$행 $y$열에 위치한 칸은 영역에 포함되어야 한다.</li> <li>$a \leq x \leq b, c \leq y \leq d$를 만족하지 않는 $1 \leq x, y \leq N$에 대해 $x$행 $y$열에 위치한 칸은 영역에 포함되지 않아야 한다.</li> </ul> </li> <li>임스는 가치가 없는 땅을 싫어하기 때문에 영역 내부에는 <strong>가치가 $0$인 칸은 없어야 한다.</strong> 즉, $(a, b, c, d)$로 정의된 영역에 대하여 $a \leq x \leq b$, $c \leq y \leq d$를 만족하는 모든 정수 $x, y$에 대해 $w_{xy} \neq 0$을 만족해야 한다.</li> <li>영역의 가치는 영역 내부 칸의 가치의 합으로 정의된다. 즉, $(a, b, c, d)$로 정의된 영역의 가치는 $\displaystyle \sum_{a \leq x \leq b \land c \leq y \leq d} w_{xy}$이다.</li> </ul> <p>하지만 임스는 가치가 없는 칸이 너무 많다는 것을 알게 되었다. 그래서 가치가 없는 칸에 건물을 건설해 가치를 올리고자 한다. 임스는 총 $K$개의 설계도를 가지고 있으며, 임스는 이 중 최대 $K$개를 사용하여 가치가 없는 칸에 건물을 건설할 수 있다.</p> <ul> <li>임스는 가지고 있는 $K$개의 설계도 중 $i$번째 설계도는 $d_{i}$의 가치를 가지고 있다.</li> <li>$d_{i}$의 가치를 가지고 있는 설계도를 사용하면 해당 칸에 가치가 $d_{i}$인 건물을 건설할 수 있으며, 이로 인해 해당 칸의 가치가 $d_{i}$ 증가한다.</li> <li>임스는 현재 가치가 없는 칸마다 설계도를 <strong>최대 한 번 사용하여</strong> 가치를 올릴 계획이다.</li> <li>한 번 사용한 설계도는 다시 사용할 수 없다.</li> </ul> <p>임스는 자신이 가지고 있는 설계도를 적절히 사용한 후, 영역 중 가치가 최대인 영역을 자신의 영역으로 정복하려고 한다. 하지만 가치가 최대인 영역이 어디인지 계산하지 못하고 있다. 임스를 도와주자!</p> ## 입력 <p>첫 번째 줄에 임스가 가지고 있는 땅의 크기를 나타내는 정수 $N$이 주어진다. $(1 \leq N \leq 500)$</p> <p>다음 $N$개의 줄에 걸쳐 $i$번째 줄에 $N$개의 음이 아닌 정수 $w_{ij}$가 공백으로 구분되어 주어진다. $(0 \leq w_{ij} \leq 9)$</p> <p>$N + 2$번째 줄에 임스가 가지고 있는 설계도의 개수 $K$가 주어진다. $(1 \leq K \leq 100 \, 000)$</p> <p>$N + 3$번째 줄에 임스가 가지고 있는 설계도의 가치 $d_{1}, d_{2}, \cdots, d_{K}$가 공백으로 구분되어 주어진다. $(1 \leq d_{i} \leq 9)$</p> ## 출력 <p>첫 번째 줄에 임스가 가진 설계도를 적절히 사용한 후 가치가 최대인 영역의 가치를 구해 출력한다.</p> ## 풀이 건물의 가치의 누적합, 0이 적인 갯수의 누적합, 새로 짓는 건물의 누적합을 가지고 N x N 브루트포스로 해결하였다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll preW[501][501], preBlank[501][501], preD[100'001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { ll w; cin >> w; if(w) preW[i][j]=w; else preBlank[i][j]++; preW[i][j] += preW[i-1][j]+preW[i][j-1]-preW[i-1][j-1]; preBlank[i][j] += preBlank[i-1][j]+preBlank[i][j-1]-preBlank[i-1][j-1]; } } int k; cin >> k; vector<ll> v(k); for(int i=0;i<k;i++) cin >> v[i]; sort(v.begin(), v.end(), greater<ll>()); for(int i=0;i<k;i++) preD[i+1] = v[i]+preD[i]; long long maxRect=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int size=1;size<=i && size<=j;size++) { int blankCnt = preBlank[i][j]-preBlank[i-size][j]-preBlank[i][j-size]+preBlank[i-size][j-size]; if(blankCnt<=k) maxRect = max(maxRect, preD[blankCnt]+preW[i][j]-preW[i-size][j]-preW[i][j-size]+preW[i-size][j-size]); else break; } } } cout << maxRect; } ```