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
#include <cstdio>
#include <vector>
#include <numeric>
#include <cstdint>

int main() {
    size_t stosow;
    size_t wysokosc;
    size_t wolno_zjesc;


    scanf("%ld %ld %ld", &stosow, &wysokosc, &wolno_zjesc);

    std::vector<uint64_t> poprzednio(wolno_zjesc+1, 0);
    std::vector<uint64_t> teraz(wolno_zjesc+1, 0);

    for (size_t i=0; i<stosow; ++i) {
        uint64_t suma_stosu = 0;
        for (size_t j=1; j <= wysokosc; ++j) {
            uint64_t nalesnik;
            scanf("%ld", &nalesnik);
            suma_stosu += nalesnik;
            //printf("suma_stosu = %ld\n", suma_stosu);
            for (size_t k=0; k < poprzednio.size() && j+k <= wolno_zjesc; ++k) {
                //size_t k;
                //if (i == 0) {
                    //k = 0;
                //} else {
                    //k = std::min(wolno_zjesc-j, wysokosc*(i-1));
                //}
                //printf("  teraz[%ld+%ld] = max(poprzednio[k]+stos=%lu, teraz[j+k]=%lu)\n", j, k, poprzednio[k]+suma_stosu, teraz[j+k]);
                teraz[j+k] = std::max(poprzednio[k] + suma_stosu, teraz[j+k]);
            }
        }
        for(size_t i=0; i<=wolno_zjesc;++i) {
            poprzednio[i] = teraz[i];
        }
    }
    printf("%lu\n", teraz[wolno_zjesc]);
}