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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>

#define ll long long
#define pi std::pair<int, int>
#define pll std::pair<ll, ll>
#define vi std::vector<int>
#define vll std::vector<ll>
#define vpi std::vector<pi>
#define vpll std::vector<pll>
#define si std::set<int>

// n * m <= 300000
// m * n log n

// musze umiec znalezc sobie sume z najlepszych rosnacych
// musze umiec znalezc tez najlepszy z poza tej sumy z odjetym kawalkiem

// czyli jak mam jakas sume S1, S2, S3, ... Sk
// wiedzac ze S1 < S2 < ... < Sk

// to wiedzac ze rozwiazanie jest w postaci pelnych sum i jakiejs uwalonej sumy
// to uwalamy albo jakas sume sposrod naszego zbioru sum

// czyli mamy S1 + S2 + S3 + ... + Sk - Px, gdzie Px jest minimalne i x nalezy od 1 do k
// ALBO mamy S1 + S2 + S3 + ... Sk-1 + Sx - Px, gdzie Sx - Px, po prostu jest maksymalne
// nalezy rowniez rozwazyc czy stosunek x do naszego zbioru, zeby wsm okreslic czy to bedzie trudne znalezc tego xa,
// NO jezeli Sx nalezy do zbioru, to jego wielkosc moze wynikac z wielkosci Sx, a nie z tego ze Sx - Px po prostu jest fajne
// czyli musimy wyznaczyc takie x zeby nie nalezalo do zbioru... i zamienic x z k, Tak tylko na chwilke

// no i znajdowanie powinno byc rzedu logarytmicznego

// z tego wynika, ze dla wygody przydaloby sie znalezc sufixy i prefixy, bo dla zbioru najwiekszych sum interesuje nas minimalny sufix // to moge ztablicowac na luzie
// a spoza zbioru interesuje nas maksymalny prefix // no to niestety bedzie sie zmieniac wiec tutaj cos musze sortowac
// moge tez sobie przygotowac kolejnosc maksymalnych sum // a no

void solve()
{
    ll n, m, k;
    std::cin >> n >> m >> k;

    std::vector<vll> tab;

    vll ordered;

    for (int i = 0; i < n; i++)
    {
        bool unordered = false;
        vll v(m);
        for (int j = 0; j < m; j++)
        {
            std::cin >> v[j];
            if (j != 0 && v[j - 1] < v[j])
                unordered = true;
        }

        if (!unordered)
            for (auto &el : v)
                ordered.push_back(el);
        else
        {
            tab.push_back(v);
        }
    }

    vpll tabpref(tab.size());
    int idxtab = 0;
    for (int i = 0; i < tab.size(); i++)
    {
        for (int j = 0; j < m; j++)
            tabpref[i].first += tab[i][j];
        tabpref[i].second = i;
    }
    std::sort(tabpref.begin(), tabpref.end(), std::greater<pll>()); // po kolei max sumy

    std::sort(ordered.begin(), ordered.end(), std::greater<ll>());

    std::vector<std::set<pll>> prefsum(m+1);
    for(int i = 0; i < tab.size(); i++) {
        ll pref = 0;
        for(int j = 0; j < tab[i].size(); j++) {
            pref += tab[i][j];
            prefsum[j+1].insert({pref, i});
        }
    }

    ll sum = 0, max = 0;
    int ordcount = 0;
    while (ordcount < ordered.size() && ordcount < k)
    {
        sum += ordered[ordcount];
        ordcount++;
    }

    int uncount = k - ordcount; // tyle ile jest elementow rosnacych
    int przerost = 0;
    vll sumsuf(m + 1, 1e18);

    while (ordcount >= 0 && uncount <= tab.size() * m)
    {
        while (przerost < uncount)
        {
            sum += tabpref[idxtab].first;
            ll suf = 0, pref = 0;
            przerost += m;
            for (int i = m - 1; i >= 0; i--) {
                pref += tab[tabpref[idxtab].second][m - i - 1];
                prefsum[m - i].erase({pref, tabpref[idxtab].second});

                suf += tab[tabpref[idxtab].second][i];
                sumsuf[m - i] = std::min(sumsuf[m - i], suf);
            }
            idxtab++;
        }

        if(uncount % m == 0)
            max = std::max(max, sum);
        else { // inaczej trzeba uwalic ten kawalek 
            int kawalek = przerost - uncount;
            ll minsuf = sumsuf[kawalek];
            max = std::max(max, sum - minsuf);
            if(!prefsum[1].empty())
                max = std::max(max, sum - tabpref[idxtab-1].first + (*std::prev(prefsum[m - kawalek].end())).first); // pamietaj by uzywac preva od enda a nie samego enda
        }

        ordcount--; uncount++; // nwm czy to dobre miejsce zobaczymy
        if(ordcount >= 0)
            sum -= ordered[ordcount]; // tak na wszelki ale to wsm dziwne
    }

    std::cout << max << '\n';
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--)
    {
        solve();
    }
}