IP
175.209.0.0
Created
08-12 08:14
1
#include <iostream>
2
#include <string.h>
3
#include <vector>
4
5
using namespace std;
6
7
int N, M, C;
8
vector<vector<int> > board;
9
10
// [start_y, start_x]부터 [start_y, start_x + M - 1] 까지 꿀을 채취할 때 얻을 수 있는 최대 값 구하기
11
// start_y: 탐색 시작하는 y 좌표
12
// start_x: 탐색 시작하는 x 좌표
13
// current_idx: 현재 채취할 꿀통의 x 좌표
14
// sum: 현재까지 채취한 꿀의 양
15
// square_sum: 현재까지 채취한 꿀의 가치
16
int select(int start_y, int start_x, int current_idx, int sum = 0, int square_sum = 0) {
17
if (sum > C) return 0;
18
if (current_idx >= start_x + M) return square_sum;
19
20
int result = 0;
21
// i를 start_x + M까지 순회하는 이유는 하나도 선택하지 않는 케이스를 위함
22
for (int i = current_idx; i <= start_x + M; i++) {
23
// i == start_x + M인 경우는 탐색할 꿀통 밖이므로 board에서 접근 할 수 없으므로 접근 못하게 조건 추가
24
if (i != start_x + M) {
25
int r1 = select(start_y, start_x, i + 1, sum + board[start_y][i],
26
square_sum + board[start_y][i] * board[start_y][i]);
27
result = max(result, r1);
28
}
29
int r2 = select(start_y, start_x, i + 1, sum, square_sum);
30
result = max(result, r2);
31
}
32
33
return result;
34
}
35
36
37
int main() {
38
ios_base::sync_with_stdio(false);
39
cin.tie(nullptr);
40
cout.tie(nullptr);
41
42
int T;
43
cin >> T;
44
45
for (int tc = 1; tc <= T; tc++) {
46
cin >> N >> M >> C;
47
48
board.clear();
49
board.resize(N, vector<int>(N, 0));
50
51
for (int i = 0; i < N; i++) {
52
for (int j = 0; j < N; j++) {
53
cin >> board[i][j];
54
}
55
}
56
57
vector<int> square;
58
for (int y = 0; y < N; y++) {
59
for (int x = 0; x <= N - M; ++x) {
60
square.push_back(select(y, x, x));
61
}
62
// 두 일꾼은 같은 줄에서 x좌표가 M만큼 떨어져 있어야 벌통이 겹치지 않으므로 아래에서 시작 지점을 M만큼 떨어트릴 것
63
// 하지만 줄이 바뀔 때는 붙어 있어도 상관없으므로 M개의 0을 각 줄 마지막에 추가해서 보완
64
for (int i = 0; i < M; ++i) {
65
square.push_back(0);
66
}
67
}
68
69
int ans = 0;
70
for (int i = 0; i < square.size(); i++) {
71
for (int j = i + M; j < square.size(); j++) {
72
ans = max(ans, square[i] + square[j]);
73
}
74
}
75
cout << "#" << tc << ' ' << ans << '\n';
76
}
77
}
78