#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int> > ert(n, vector<int>(m));
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> ert[i][j];
}
}
vector<vector<int> > dp(n, vector<int>(m, INT_MAX));
dp[0][0]=ert[0][0];
for (int j=m-1; j>=0; j--) {
for (int i=n-1; i>=0; i--) {
if (i!=n-1) {
dp[i][j]=min(dp[i][j], dp[i+1][j]+ert[i][j]);
}
if (j!=m-1) {
dp[i][j]=min(dp[i][j], dp[i][j+1]+ert[i][j]);
}
}
}
/*cout << "\n";
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cout << dp[i][j] << " ";
}
cout << "\n";
}*/
vector<int> visszafejt;
int x=0, y=0;
visszafejt.push_back(ert[0][0]);
//cout << "\n";
while (x<n && y<m) {
//cout << x << " " << y << "\n";
if (x<n-1 && dp[x][y]==dp[x+1][y]+ert[x][y]) {
x++;
}
else {
y++;
}
visszafejt.push_back(ert[x][y]);
}
for (int i=0; i<k; i++) {
int maxi=0, hely=0;
for (int j=0; j<visszafejt.size(); j++) {
if (maxi<visszafejt[j]) {
maxi=visszafejt[j];
hely=j;
}
}
visszafejt[hely]/=2;
/*for (int j=0; j<visszafejt.size(); j++) {
cout << visszafejt[j] << " ";
}
cout << "\n";*/
}
int veg=0;
for (int j=0; j<visszafejt.size(); j++) {
veg+=visszafejt[j];
//cout << visszafejt[j] << " ";
}
cout << veg << endl;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 18/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1684 KiB | |||
2 | Hibás válasz | 0/0 | 3ms | 1948 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2076 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2284 KiB | |||
5 | Elfogadva | 3/3 | 3ms | 2496 KiB | |||
6 | Elfogadva | 3/3 | 3ms | 2708 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2920 KiB | |||
8 | Elfogadva | 3/3 | 3ms | 3132 KiB | |||
9 | Hibás válasz | 0/2 | 3ms | 3480 KiB | |||
10 | Hibás válasz | 0/2 | 3ms | 3524 KiB | |||
11 | Hibás válasz | 0/3 | 3ms | 3668 KiB | |||
12 | Hibás válasz | 0/3 | 2ms | 3684 KiB | |||
13 | Hibás válasz | 0/2 | 3ms | 3676 KiB | |||
14 | Elfogadva | 3/3 | 3ms | 3712 KiB | |||
15 | Hibás válasz | 0/2 | 3ms | 3636 KiB | |||
16 | Hibás válasz | 0/3 | 3ms | 3716 KiB | |||
17 | Hibás válasz | 0/2 | 3ms | 3928 KiB | |||
18 | Hibás válasz | 0/3 | 3ms | 4140 KiB | |||
19 | Hibás válasz | 0/2 | 3ms | 4224 KiB | |||
20 | Hibás válasz | 0/3 | 3ms | 4228 KiB | |||
21 | Hibás válasz | 0/2 | 3ms | 4348 KiB | |||
22 | Hibás válasz | 0/3 | 3ms | 4432 KiB |