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
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, m, k, s, i, j, o;
    cin >> n >> m >> k;
    
    vector <ll> dp(k+1, 0);
    for (i=0; i<n; ++i){
        vector <ll> a(m);
        for (j=0; j<m; ++j)
            cin >> a[j];
        
        vector <ll> dp2=dp;
        for (j=0; j<k; ++j){
            s = 0;
            for (o=0; o<m && j+o+1<=k; ++o){
                s += a[o];
                dp2[j+o+1] = max(dp2[j+o+1], dp[j] + s);
            }
        }
        dp = dp2;
    }
    
    cout << dp[k] << '\n';

    return 0;
}