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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// Author : Jakub Rożek
// Task   : STO - Stosy naleśników [B]
// Time   : n * m * log(n * m)
// Memory : n * m

// Stosy dzielimy na 2 grupy i przeiterujemy się po kazdej parze a,b a+b = nm i weźmiemy z danej grupy.
// 1. Od największych do najmniejszych - sortuje wszystkie razem i licze sume prefixową - opłaca sie brać na pałę.
// 2. Stosy od najmniejszego do największego.
// Kluczowa obserwacja to jak biore jakiś stos to biore go do końca (lub tylko 1 do połowy).
// ...

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 2000000000000000000;

struct SmallStack {
    ll sum = 0;
    vector<ll> prefix;
};

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<ll> big_values;      // Naleśniki ze stosow od największych do najmniejszych (trzymamy razem).
    vector<SmallStack> stacks;  // Stosy z małymi naleśnikami.

    for (int i = 0; i < n; ++i) {
        vector<ll> values(m);
        for (int j = 0; j < m; ++j) {
            cin >> values[j];
        }
        // Duże naleśniki.
        if (m == 1 || values[0] >= values[m-1]) {
            for (ll v : values) {
                big_values.push_back(v);
            }
            continue;
        }
        // Małe naleśniki.
        SmallStack current;
        current.prefix.resize(m + 1, 0);
        for (int j = 0; j < m; ++j) {
            current.sum += values[j];
            current.prefix[j + 1] = current.sum;
        }
        stacks.push_back(current);
    }

    const int p = (int)stacks.size();
    const int small_quantity = p * m;
    const int big_quantity = (int)big_values.size();

    big_values.push_back(INF);
    sort(big_values.rbegin(), big_values.rend());
    big_values[0] = 0;
    for (int i = 1; i <= big_quantity; ++i) {
        big_values[i] += big_values[i-1];
    }

    if (p == 0) {
        cout << big_values[k] << '\n';
        return 0;
    }

    stacks.push_back({INF,{}});
    sort(
        stacks.begin(),
        stacks.end(),
        [](const SmallStack& left, const SmallStack& right) {
            return left.sum > right.sum;
        }
    );

    // Dla każdej reszty licze jaka jest najlepsza suma na prefiksie i sufiksie stosów.
    vector<vector<ll>> prefix_best(m, vector<ll>(p + 1, 0));    // najmniejsza suma - prefix
    vector<vector<ll>> suffix_best(m, vector<ll>(p + 1, 0));    // normalna
    for (int r = 1; r < m; ++r) {
        ll current_best = -INF;
        for (int i = 1; i <= p; ++i) {
            current_best = max(current_best, stacks[i].prefix[r] - stacks[i].sum);
            prefix_best[r][i] = current_best;
        }
        current_best = -INF;
        for (int i = p; i >= 1; --i) {
            current_best = max(current_best, stacks[i].prefix[r]);
            suffix_best[r][i] = current_best;
        }
    }

    vector<ll> small_values(small_quantity + 1, 0); // Suma prefixxowa grupy małych naleśników.
    vector<ll> full_prefix(p + 1, 0);               // Suma prefiksowa sumy stosow.
    for (int i = 1; i <= p; ++i) {
        full_prefix[i] = full_prefix[i-1] + stacks[i].sum;
    }

    // dla każdej ilości full i reszty licze ile najwięcej da naleśników.
    for (int f = 0; f <= p; ++f) {
        small_values[f * m] = full_prefix[f];
        if (f == p) break;
        for (int r = 1; r < m; ++r) {
            // Częściowy stos poza pierwszymi pełnymi.
            ll best_value = full_prefix[f] + suffix_best[r][f + 1];
            // Częściowy stos jest wśród pierwszych pełnych
            if (f >= 1) {
                best_value = max(best_value, full_prefix[f + 1] + prefix_best[r][f]);
            }
            small_values[f * m + r] = best_value;
        }
    }

    // Łącze zbiór dużych i małych naleśników.
    ll answer = -INF;
    for (int i = max(0, k-big_quantity); i <= min(k, small_quantity); ++i) {
        answer = max(answer, small_values[i] + big_values[k - i]);
    }

    cout << answer << '\n';
    return 0;
}