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

const long long guard = 1e18;
vector<long long> separateFlipped(int n, int m, vector<vector<long long>> &pancakes) {
    vector<long long> flipped(n*m + 1, 0);
    flipped[0] = guard;         //we want to have `0` at flipped[0], bc prefix
    int pos = 1;

    int end = n-1;
    for(int i=0; i<=end; i++) {
        if(pancakes[i][0] >= pancakes[i][m-1]) {            //is flipped (or equal all the way up)
            for(int j=0; j<m; j++)
                flipped[pos++] = pancakes[i][j];
            swap(pancakes[i--], pancakes[end--]);         //remove that pile
            pancakes.pop_back();
        }
        //else - leave it
    }

    sort(flipped.begin(), flipped.end(), greater<>());
    flipped[0] = 0;         //it was `guard`, now it's removed
    for(int i=1; i<=n*m; i++)
        flipped[i] += flipped[i-1];         //make prefix

    return flipped;
}

typedef priority_queue<pair<long long, int>> maxQueue;
typedef priority_queue<long long, vector<long long>, greater<>> minQueue;
vector<long long> calculateRest(int n, int m, vector<vector<long long>> &pancakes) {
    int size = n*m;
    n = pancakes.size();
    for(int i=0; i<n; i++)          //make prefix sum
        for(int j=1; j<m; j++)
            pancakes[i][j] += pancakes[i][j-1];

    vector<pair<long long, int>> sums(n+1);         //{sum, index}, also prefix sum
    sums[0] = {guard, -1};
    for(int i=0; i<n; i++)
        sums[i+1] = {pancakes[i][m-1], i};
    sort(sums.begin(), sums.end(), greater<>());
    sums[0].first = 0;
    for(int i=1; i<=n; i++)
        sums[i].first += sums[i-1].first;
    vector<int> order(n);
    for(int i=1; i<=n; i++)
        order[sums[i].second] = i;

    vector<maxQueue> tops(m);           //offset by 1, meaning tops[i] contains top of pile of size i+1
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            tops[j].emplace(pancakes[i][j], i);

    vector<long long> bottoms(m-1, guard);  //smallest bottom of each size (offset by 1), only from 'currently used piles + the very next one'

    vector<long long> normal(size+1, 0);            //to be a prefix sum
    for(int k=0; k<n*m; k++) {
        int piles = k/m;
        int remainder = k%m;
        if(remainder == 0) {            //only complete piles
            normal[k] = sums[piles].first;
            //update bottoms
            int nextPileIndex = sums[piles+1].second;
            for(int j=1; j<m; j++)          //bottom of size j
                bottoms[j-1] = min(bottoms[j-1], pancakes[nextPileIndex][m-1] - pancakes[nextPileIndex][m-1-j]);
        }
        else {          //one incomplete pile
            long long addTop = sums[piles].first;
            while(order[tops[remainder-1].top().second] <= piles)
                tops[remainder-1].pop();
            addTop += tops[remainder-1].top().first;

            long long removeBottom = sums[piles+1].first;
            int toRemove = m - remainder;
            removeBottom -= bottoms[toRemove-1];

            normal[k] = max(addTop, removeBottom);
        }
    }

    for(int k=n*m; k<=size; k++)
        normal[k] = sums[n].first;

    return normal;
}

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> pancakes(n, vector<long long>(m));
    for(auto &v: pancakes)
        for(auto &a : v)
            cin >> a;

    vector<long long> flipped = separateFlipped(n, m, pancakes);

    vector<long long> normal = calculateRest(n, m, pancakes);

    long long result = 0;
    for(int i=0; i<=k; i++)
        result = max(result, normal[i] + flipped[k-i]);
    cout << result << "\n";

    return 0;
}