1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> dp(k + 7);
    vector<vector<ll>> s(n, vector<ll>(m, 0));
    for (ll i = 0; i < n; ++i){
        for (ll j = 0; j < m; ++j){
            cin >> s[i][j];
            if (j > 0) s[i][j] += s[i][j - 1];
        }
    }
    for (ll i = 0; i < n; ++i){ // idziemy po wszystkich stosach
        for (ll j = k - 1; j >= 0; --j){ // idziemy po wszystkich pozycjach
            if (dp[j] != 0 or j == 0)
            for (ll k = 0; k < m; ++k){
                
                dp[j + k + 1] = max(dp[j + k + 1], dp[j] + s[i][k]);
            }
        }
    }
    ll maxw = 0;
    for (ll i = 0; i <= k; ++i){
        maxw = max(maxw, dp[i]);
    }
    cout << maxw << endl;
}