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

using namespace std;

const int maxN=3e5;

long long n, m, k, decNum=0, incNum=0, decRes[maxN], incRes[maxN], result=0;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>k;
    vector<vector<long long>>dec(n), inc(n);//2*needed memory
    priority_queue<pair<long long, long long>>PQ;
    for(int i=0; i<n; i++){
        vector<long long>v(m);
        for(int j=0; j<m; j++){
            cin>>v[j];
        }
        if(m == 1 || v[0] > v[1]){
            reverse(v.begin(), v.end());
            PQ.push({v.back(), decNum/m});
            dec[decNum/m] = v;
            decNum += m;
        }
        else{
            inc[incNum/m] = v;
            incNum += m;
        }
    }

    for(int i=1; i<=decNum; i++){
        pair<long long, int>val = PQ.top();
        PQ.pop();
        dec[val.second].pop_back();
        if(!dec[val.second].empty())PQ.push({dec[val.second].back(), val.second});
        decRes[i] = decRes[i-1] + val.first;
    }

    vector<pair<long long, int>>topVals;
    multiset<long long>incMS[m];
    long long** ps = new long long*[incNum/m];
    for(int i=0; i<incNum/m; i++){
        ps[i] = new long long[m];
        ps[i][0]=inc[i][0];
        incMS[0].insert(ps[i][0]);
        for(int j=1; j<m; j++){
            ps[i][j] = inc[i][j]+ps[i][j-1];
            incMS[j].insert(ps[i][j]);
        }
        topVals.push_back({ps[i][m-1], i});
    }
    sort(topVals.begin(), topVals.end());
    reverse(topVals.begin(), topVals.end());
    topVals.push_back({-1, -1});

    long long baseRes=0, prevIdx=0;
    for(int i=0; i<topVals.size()-1; i++){
        for(int j=0; j<m; j++){
            incRes[i*m+j+1]=*incMS[j].rbegin()+baseRes;
        }
        baseRes += topVals[i].first;
        if(topVals[i].first != topVals[i+1].first){
            for(int j=prevIdx; j<=i; j++){
                for(int k=0; k<m; k++){
                    incMS[k].erase(incMS[k].find(ps[topVals[j].second][k]));
                }
            }
            prevIdx = i+1;
        }
    }

    for(int i=0; i<=k; i++)if(i <= decNum && k-i <= incNum)result = max(result, decRes[i]+incRes[k-i]);
    cout<<result;
    return 0;
}