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
127
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll jebane_inf = -(1LL << 60);

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

    int stosiki, wysokosc, wpierdol;
    cin >> stosiki >> wysokosc >> wpierdol;

    vector<vector<ll>> rosna_pref;
    vector<vector<ll>> maleja;

    for (int i = 0; i < stosiki; i++) {
        vector<ll> tab(wysokosc);
        for (int j = 0; j < wysokosc; j++) cin >> tab[j];

        if (tab[0] <= tab.back()) {
            vector<ll> pref(wysokosc + 1, 0);
            for (int j = 0; j < wysokosc; j++) pref[j + 1] = pref[j] + tab[j];
            rosna_pref.push_back(pref);
        } else {
            maleja.push_back(tab);
        }
    }

    int ile_rosnie = (int)rosna_pref.size();
    int ile_maleje = (int)maleja.size();

    vector<ll> ros(wpierdol + 1, jebane_inf), male(wpierdol + 1, jebane_inf);
    ros[0] = 0;
    male[0] = 0;

    if (ile_rosnie > 0) {
        vector<int> kolejnosc(ile_rosnie);
        iota(kolejnosc.begin(), kolejnosc.end(), 0);

        vector<ll> sumki(ile_rosnie);
        for (int i = 0; i < ile_rosnie; i++) sumki[i] = rosna_pref[i][wysokosc];

        sort(kolejnosc.begin(), kolejnosc.end(), [&](int a, int b) {
            return sumki[a] > sumki[b];
        });

        vector<vector<ll>> poukladane(ile_rosnie, vector<ll>(wysokosc + 1));
        vector<ll> poukladane_sumki(ile_rosnie);

        for (int i = 0; i < ile_rosnie; i++) {
            poukladane[i] = rosna_pref[kolejnosc[i]];
            poukladane_sumki[i] = sumki[kolejnosc[i]];
        }

        vector<ll> pref_sumikow(ile_rosnie + 1, 0);
        for (int i = 0; i < ile_rosnie; i++) pref_sumikow[i + 1] = pref_sumikow[i] + poukladane_sumki[i];

        int limit_ros = min(wpierdol, ile_rosnie * wysokosc);

        for (int ile_caluchnych = 0; ile_caluchnych <= ile_rosnie; ile_caluchnych++) {
            int x = ile_caluchnych * wysokosc;
            if (x <= limit_ros) ros[x] = pref_sumikow[ile_caluchnych];
        }

        for (int reszta = 1; reszta < wysokosc; reszta++) {
            if (reszta > limit_ros) break;

            vector<ll> pref_max(ile_rosnie), suf_max(ile_rosnie);

            for (int i = 0; i < ile_rosnie; i++) {
                ll cosik = poukladane[i][reszta] - poukladane_sumki[i];
                if (i == 0) pref_max[i] = cosik;
                else pref_max[i] = max(pref_max[i - 1], cosik);
            }

            for (int i = ile_rosnie - 1; i >= 0; i--) {
                ll cosik = poukladane[i][reszta];
                if (i == ile_rosnie - 1) suf_max[i] = cosik;
                else suf_max[i] = max(suf_max[i + 1], cosik);
            }

            int max_caluchnych = min(ile_rosnie - 1, (limit_ros - reszta) / wysokosc);

            for (int ile_caluchnych = 0; ile_caluchnych <= max_caluchnych; ile_caluchnych++) {
                ll wynikowy_smiech = pref_sumikow[ile_caluchnych] + suf_max[ile_caluchnych];
                if (ile_caluchnych > 0) {
                    wynikowy_smiech = max(wynikowy_smiech, pref_sumikow[ile_caluchnych + 1] + pref_max[ile_caluchnych - 1]);
                }
                ros[ile_caluchnych * wysokosc + reszta] = wynikowy_smiech;
            }
        }
    }

    if (ile_maleje > 0) {
        priority_queue<tuple<ll,int,int>> kopiec;

        for (int i = 0; i < ile_maleje; i++) {
            kopiec.push({maleja[i][0], i, 0});
        }

        int limit_mal = min(wpierdol, ile_maleje * wysokosc);

        for (int ile = 1; ile <= limit_mal; ile++) {
            auto [mniam, ktory, gdzie] = kopiec.top();
            kopiec.pop();

            male[ile] = male[ile - 1] + mniam;

            if (gdzie + 1 < wysokosc) {
                kopiec.push({maleja[ktory][gdzie + 1], ktory, gdzie + 1});
            }
        }
    }

    ll wynikowy_bebzol = 0;

    for (int z_rosnacych = 0; z_rosnacych <= wpierdol; z_rosnacych++) {
        int z_malejacych = wpierdol - z_rosnacych;
        if (ros[z_rosnacych] == jebane_inf) continue;
        if (male[z_malejacych] == jebane_inf) continue;
        wynikowy_bebzol = max(wynikowy_bebzol, ros[z_rosnacych] + male[z_malejacych]);
    }

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