IP
175.209.0.0
Created
08-12 07:37
1
#include <iostream>
2
#include <vector>
3
4
using namespace std;
5
6
7
int N, M, C;
8
9
int select(vector<int> v, int remain, int idx = 0, int sum = 0, int square_sum = 0) {
10
if (sum > C) return 0;
11
if (remain == 0) return square_sum;
12
13
if (idx >= v.size()) {
14
return square_sum;
15
}
16
17
int result = 0;
18
for (int i = idx; i <= v.size(); i++) {
19
if (i != v.size()) {
20
int r1 = select(v, remain - 1, i + 1, sum + v[i], square_sum + v[i] * v[i]);
21
result = max(result, r1);
22
}
23
int r2 = select(v, remain, i + 1, sum, square_sum);
24
result = max(result, r2);
25
}
26
27
return result;
28
}
29
30
31
int main() {
32
ios_base::sync_with_stdio(false);
33
cin.tie(nullptr);
34
cout.tie(nullptr);
35
36
int T;
37
cin >> T;
38
39
for (int tc = 1; tc <= T; tc++) {
40
cin >> N >> M >> C;
41
42
vector<vector<int> > board(N, vector<int>(N, 0));
43
for (int i = 0; i < N; i++) {
44
for (int j = 0; j < N; j++) {
45
cin >> board[i][j];
46
}
47
}
48
49
vector<int> square;
50
51
for (int y = 0; y < N; y++) {
52
for (int x = 0; x <= N - M; ++x) {
53
int result = select(vector<int>(board[y].begin() + x, board[y].begin() + x + M), M);
54
square.push_back(result);
55
}
56
for (int i = 0; i < M; ++i) {
57
square.push_back(0);
58
}
59
}
60
61
int ans = 0;
62
63
for (int i = 0; i < square.size(); i++) {
64
for (int j = i + M; j < square.size(); j++) {
65
ans = max(ans, square[i] + square[j]);
66
}
67
}
68
cout << "#" << tc << ' ' << ans << '\n';
69
}
70
}
71