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
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef unsigned long long int ulli;

int n, m, k;
vector<ulli> pancakes_from_desc_stacks;
vector<vector<ulli> > asc_sums;
vector<ulli> tmp, desc, asc;

int main() {

    // Read input
    scanf("%d %d %d", &n, &m, &k);
    tmp.resize(m);
    FOR(i,0,n) {
        bool is_asc = false;
        FOR(j,0,m) {
            scanf("%lld", &tmp[j]);
            if (j > 0 && tmp[j] > tmp[j-1])
                is_asc=true;
        }
        if (is_asc) {
            FOR(j,1,m) tmp[j] += tmp[j-1];
            asc_sums.push_back(tmp);
        } else {
            FOR(j,0,m) pancakes_from_desc_stacks.push_back(tmp[j]);
        }
    }

    // Calculate options for DESC pancakes
    desc.resize(pancakes_from_desc_stacks.size() + 1, 0);
    sort(pancakes_from_desc_stacks.begin(), pancakes_from_desc_stacks.end());
    reverse(pancakes_from_desc_stacks.begin(), pancakes_from_desc_stacks.end());
    FOR(i,0,pancakes_from_desc_stacks.size()) desc[i+1] = desc[i] + pancakes_from_desc_stacks[i];

    // Calculate options for ASC pancakes
    asc.resize(n*m - pancakes_from_desc_stacks.size() + 1, 0);
    FOR(depth,1,m+1) {
        // Prepare stacks parameters, sorted descending by sum of whole stacks
        vector<pair<ulli, ulli> > S(asc_sums.size());
        FOR(i,0,S.size()) S[i] = make_pair(asc_sums[i][m-1], asc_sums[i][depth-1]);
        sort(S.begin(), S.end());
        reverse(S.begin(), S.end());

        // Prepare prefix/suffix tables
        vector<ulli> full_from_start(S.size());
        vector<ulli> min_diff_from_start(S.size());
        vector<ulli> max_half_from_end(S.size());
        FOR(i,0,S.size()) {
            full_from_start[i] = S[i].first;
            min_diff_from_start[i] = S[i].first - S[i].second;
            max_half_from_end[S.size()-i-1] = S[S.size()-i-1].second;
            if (i>0) {
                full_from_start[i] += full_from_start[i-1];
                min_diff_from_start[i] = min(min_diff_from_start[i], min_diff_from_start[i-1]);
                max_half_from_end[S.size()-i-1] = max(max_half_from_end[S.size()-i-1], max_half_from_end[S.size()-i]);
            }
        }

        // Make core calculations
        FOR(i,0,S.size()) {
            if (i==0) asc[i*m + depth] = max_half_from_end[0];
            else asc[i*m + depth] = max(
                full_from_start[i-1] + max_half_from_end[i],    // Option 1
                full_from_start[i] - min_diff_from_start[i]     // Option 2
            );
        }
    }

    // Construct result
    ulli result = 0;
    FOR(i,0,k+1)
        if (i < desc.size() && k-i < asc.size())
            result = max(result, desc[i] + asc[k-i]);
    printf("%lld\n", result);
    return 0;
}