#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0), ios::sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> board(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
}
}
// what is the min cost of getting to [i;j] with d dynamites
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(k + 1, INT_MAX / 2)));
dp[1][1][0] = board[1][1];
for (int d = 1; d <= k; d++)
dp[1][1][d] = dp[1][1][d - 1] / 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int d = 0; d <= k; d++) {
for (int dd = 0; dd <= d; dd++) {
dp[i][j][d] = min(dp[i][j][d], (board[i][j] >> dd) + min(dp[i][j - 1][d - dd], dp[i - 1][j][d - dd]));
}
}
}
}
cout << dp[n][m][k];
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1832 KiB | |||
2 | Elfogadva | 0/0 | 6ms | 2740 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2496 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2588 KiB | |||
5 | Elfogadva | 3/3 | 3ms | 2552 KiB | |||
6 | Elfogadva | 3/3 | 3ms | 2672 KiB | |||
7 | Elfogadva | 2/2 | 6ms | 3244 KiB | |||
8 | Elfogadva | 3/3 | 6ms | 3444 KiB | |||
9 | Elfogadva | 2/2 | 3ms | 2864 KiB | |||
10 | Elfogadva | 2/2 | 3ms | 2944 KiB | |||
11 | Elfogadva | 3/3 | 3ms | 2864 KiB | |||
12 | Elfogadva | 3/3 | 3ms | 3120 KiB | |||
13 | Elfogadva | 2/2 | 3ms | 3144 KiB | |||
14 | Elfogadva | 3/3 | 3ms | 3400 KiB | |||
15 | Elfogadva | 2/2 | 6ms | 3820 KiB | |||
16 | Elfogadva | 3/3 | 6ms | 3832 KiB | |||
17 | Elfogadva | 2/2 | 6ms | 4096 KiB | |||
18 | Elfogadva | 3/3 | 6ms | 3972 KiB | |||
19 | Elfogadva | 2/2 | 6ms | 4224 KiB | |||
20 | Elfogadva | 3/3 | 6ms | 4332 KiB | |||
21 | Elfogadva | 2/2 | 6ms | 4204 KiB | |||
22 | Elfogadva | 3/3 | 6ms | 4332 KiB |