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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;

bool porownaj (const pair <ll,vector <ll>> &lhs, const pair <ll,vector <ll>> &rhs) {
    return lhs.first >rhs.first;
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m,k;
    cin >> n >> m >> k;
    vector <vector <ll>> stosyMal;
    vector <pair <ll, vector <ll>>> stosyRosn;
    priority_queue <pair <ll,ll>> pq;
    for (int i = 0; i < n; i++) {
        vector <ll> a(m);
        bool czyMalejacy = true;
        for (int j = 0; j < m; j++) {
            cin >> a[j];
        }
        for (int j = 1; j < m; j++) {
            if (a[j-1] < a[j]) {
                czyMalejacy = false;
                break;
            }
        }
        if (czyMalejacy) {
            stosyMal.push_back(a);
            pq.push({a[0],stosyMal.size()-1});
        } else {
            vector <ll> tym(m+1);
            ll suma = 0;
            for (int j = 0; j < m; j++) {
                suma+=a[j];
                tym[j+1] = tym[j]+a[j];
            }
            stosyRosn.push_back({suma,tym});
        }
    }
    vector <int> poz(stosyMal.size());
    int ileTrzeba = k;
    int ile = 0;
    vector <ll> wynMal(k+1);
    while (ile != ileTrzeba && !pq.empty()) {
        auto [wart,nr] = pq.top();
        pq.pop();
        ile++;
        wynMal[ile] = wynMal[ile-1]+wart;
        poz[nr]++;
        if (poz[nr] < m) pq.push({stosyMal[nr][poz[nr]],nr});
    }
    for (int i = ile+1; i < ileTrzeba; i++) wynMal[i] = wynMal[i-1];
    vector <ll> wynRos(k+1);
    if (stosyRosn.size() == 0) {
        cout << wynMal[k] << "\n";
        return 0;
    }
    sort(stosyRosn.begin(), stosyRosn.end(), porownaj);
    vector <ll> calkSumaPierwszych(stosyRosn.size()+1);
    for (int i = 0; i < stosyRosn.size(); i++) {
        calkSumaPierwszych[i+1] = calkSumaPierwszych[i]+stosyRosn[i].first;
    }
    ll gran = min(k, m*(ll)stosyRosn.size());
    vector <ll> ilePierwsze(stosyRosn.size()), ileTracimy(stosyRosn.size()), sufPierwsze(stosyRosn.size()+1), PrefTracimy(stosyRosn.size()+1);
    for (int i = 0; i <stosyRosn.size(); i++) {
        if ((i+1)*m > gran) continue; 
        wynRos[(i+1)*m] = calkSumaPierwszych[i+1];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < stosyRosn.size(); j++) {
            auto &pref = stosyRosn[j].second;
            ilePierwsze[j] = pref[i];
            ileTracimy[j] = pref[i]-stosyRosn[j].first;

        }
        PrefTracimy[0] = ileTracimy[0];
        for (int j = 1; j < stosyRosn.size(); j++) {
            PrefTracimy[j] = max(PrefTracimy[j-1],ileTracimy[j]);
        }
        sufPierwsze[stosyRosn.size()] = 0;
        sufPierwsze[stosyRosn.size()-1] = ilePierwsze[stosyRosn.size()-1];
        for (int j = stosyRosn.size()-2; j >= 0; j--) {
            sufPierwsze[j] = max(sufPierwsze[j+1], ilePierwsze[j]);
            //cout << j << " " << sufPierwsze[j] << "  ";
        }
        for (int j = 0; j < stosyRosn.size(); j++) {
            ll ile = j*m+i;
            if (ile > gran) continue;
            ll wart = calkSumaPierwszych[j]+sufPierwsze[j];
            if (j >= 1) wart = max(wart,calkSumaPierwszych[j+1]+PrefTracimy[j]);
            //cout << ile << " " << calkSumaPierwszych[j] << "  ";
            wynRos[ile] = wart;
        }
    }
    ll wynik = 0;
    for (int i = 0; i <= k; i++) {
        //cout << k-i << " " << wynRos[k-i] << " " << wynMal[i] << "\n";
        wynik = max(wynik,wynMal[i]+wynRos[k-i]);
    }
    cout << wynik << "\n";
    return 0;
}