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

const int base = 1 << 19;
vector<int> stos[base];
int ind_i[base];
priority_queue<pair<int, int>> kol_desc;
int ans_inc[base], ans_desc[base];
long long INF = 1'000'000'000'000'000'009;

//increasing stuff
vector<int> pref_sum[base];
multiset<pair<int, int>> s[base]; //sety majace wartosci o danej reszcie modulo
priority_queue<pair<int, int>> kol_inc[base]; //kolejka trzymajaca najmniejsze sufiksy
bool used_stack[base];

int32_t main(){

    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        bool inc = true;
        for(int j = 0; j < m; j++){
            int x; cin >> x; stos[i].push_back(x);
            if(j > 0 && stos[i][j - 1] > x) inc = false;
        }
        ind_i[i] = 1; //decreasing stuff

        if(inc == true){
            int temp_sum = 0;
            for(int j = 0; j < m; j++){
                temp_sum += stos[i][j];
                pref_sum[i].push_back(temp_sum);
                s[j + 1].insert({temp_sum, i}); //chodzi o reszte modulo!!!
            }
        }
        else kol_desc.push({stos[i][0], i});
    }

    int whole_sum = 0, ac_index = 1; //suma ze wszystkich poprzednich calosci, aktualny index
    bool is_good = true;
    while(ac_index <= k){
        for(int i = 0; i < m; i++){
            if(s[i + 1].empty()) {is_good = false; break;};

            auto [value, ind] = *s[i + 1].rbegin();
            while(!s[i + 1].empty() && used_stack[s[i + 1].rbegin()->second]){
                auto it = prev(s[i + 1].end());
                s[i + 1].erase(it);
            }
            if(s[i + 1].empty()) {is_good = false; break;}
            tie(value, ind) = *s[i + 1].rbegin();

            ans_inc[ac_index] = whole_sum + value;

            //second case, gdzie podmieniamy nasze coski
            if(!kol_inc[i + 1].empty()){
                int ind_temp = kol_inc[i + 1].top().second; //potrzebujemy tylko tego indexu
                ans_inc[ac_index] = max(ans_inc[ac_index], whole_sum + pref_sum[ind][m - 1] - pref_sum[ind_temp][m - 1] + pref_sum[ind_temp][i]);
            }

            ac_index++;
        }
        if(is_good == false) break;

        //musimy odchaczyc, ze juz uzylismy ten ostatni cosiek
        auto [value, ind] = *s[m].rbegin();
        for(int i = 0; i < m; i++)
            kol_inc[i + 1].push({-(pref_sum[ind][m - 1] - pref_sum[ind][i]), ind}); //wrzucamy na kolejke najmniejsza roznice

        used_stack[ind] = true;
        whole_sum += value;
    }

    int res_desc = 0;
    for(int i = 1; i <= k; i++){//building decreasing value
        if(!kol_desc.empty()){
            int val = kol_desc.top().first, ind = kol_desc.top().second;
            kol_desc.pop();
            res_desc += val;
            ans_desc[i] = res_desc;
            if(ind_i[ind] < m){
                kol_desc.push({stos[ind][ind_i[ind]], ind});
                ind_i[ind]++;
            }
        }
        else
            ans_desc[i] = -INF;
    }

    ans_desc[0] = 0; ans_inc[0] = 0;
    int res = 0;
    for(int i = 0; i <= k; i++)
        res = max(ans_inc[i] + ans_desc[k - i], res);
    cout << res;
    return 0;
}