25 lines
599 B
C++
25 lines
599 B
C++
|
#include <cstring>
|
||
|
|
#include <iostream>
|
||
|
|
|
||
|
|
using namespace std;
|
||
|
|
#define maxn 10005
|
||
|
|
#define M 105
|
||
|
|
int dp[maxn];
|
||
|
|
int w[M][M];
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
int T, n, W;
|
||
|
|
cin >> T >> n >> W;
|
||
|
|
for (int i = 1; i <= T; i++)
|
||
|
|
for (int j = 1; j <= n; j++) // <- used to be i++
|
||
|
|
cin >> w[i][j];
|
||
|
|
for (int i = 1; i < T; i++) {
|
||
|
|
memset(dp, 0, sizeof dp);
|
||
|
|
for (int j = 1; j <= n; j++)
|
||
|
|
for (int k = w[i][j]; k <= W; k++)
|
||
|
|
dp[k] = max(dp[k], dp[k - w[i][j]] + w[i + 1][j] - w[i][j]);
|
||
|
|
W = max(dp[W] + W, W);
|
||
|
|
}
|
||
|
|
cout << W << endl;
|
||
|
|
return 0;
|
||
|
|
}
|