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
#include <iostream>
#include <algorithm>
using namespace std;

long long dp[300001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;

    long long a[n][m];
    long long pref[n][m+1];
    for(int i = 0; i < n; i++) {
        pref[i][0] = 0;
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
            pref[i][j+1] = pref[i][j] + a[i][j];
        }
    }

    for(int i = 0; i < n; i++) {
        for(int q = k; q >= 0; q--) {
            for(int j = 0; j <= q && j <= m; j++) {
                dp[q] = max(dp[q], dp[q - j] + pref[i][j]);
            }
        }
    }
    cout << dp[k] << "\n"; 
    return 0;
}