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
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long liczba_stosow, naleśniki_w_stosie, ile_je_nalesnikow;
    cin >> liczba_stosow >> naleśniki_w_stosie >> ile_je_nalesnikow;

    // stosy[i][j] = rozmiar j-tego naleśnika w i-tym stosie
    vector<vector<long long>> stosy(liczba_stosow, vector<long long>(naleśniki_w_stosie));
    // prefiksy[i][t] = suma pierwszych t naleśników z i-tego stosu
    vector<vector<long long>> prefiksy(liczba_stosow, vector<long long>(naleśniki_w_stosie + 1, 0));

    for (long long i = 0; i < liczba_stosow; i++) {
        for (long long j = 0; j < naleśniki_w_stosie; j++) {
            cin >> stosy[i][j];
        }
        // jeśli stos jest rosnący, odwracamy kolejność
        if (naleśniki_w_stosie > 1 && stosy[i][0] < stosy[i][1]) {
            reverse(stosy[i].begin(), stosy[i].end());
        }
        // obliczamy prefiksy sum
        for (long long j = 1; j <= naleśniki_w_stosie; j++) {
            prefiksy[i][j] = prefiksy[i][j-1] + stosy[i][j-1];
        }
    }

    // dp[x] = maksymalna suma rozmiarów dla dokładnie x naleśników
    vector<long long> dp(ile_je_nalesnikow + 1, 0);

    for (long long i = 0; i < liczba_stosow; i++) {
        for (long long x = ile_je_nalesnikow; x >= 0; x--) {
            for (long long t = 1; t <= naleśniki_w_stosie && t <= x; t++) {
                dp[x] = max(dp[x], dp[x - t] + prefiksy[i][t]);
            }
        }
    }

    cout << dp[ile_je_nalesnikow] << "\n";

    return 0;
}