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

#define int long long

using namespace std;

signed main(){

cin.tie(0) -> sync_with_stdio(0);

int n,m,k;
cin>>n>>m>>k;

vector<vector<int>> v(n);
vector<vector<int>> pref(n, vector<int> (m, 0));
vector<char> czy(n, 0);
vector<int> ile(n, 0);

for(int i=0;i<n;i++){
    v[i].resize(m);
    for(auto &x : v[i]){
        cin>>x;
    }
}

for(int i=0;i<n;i++){
    if(m > 1){
        if(v[i][0] < v[i][1]){
            czy[i] = 1;
        }
    }
    pref[i][0] = v[i][0];
    for(int j=1;j<m;j++){
        pref[i][j] = pref[i][j-1]+v[i][j];
    }
    ile[i] = pref[i].back();
}

vector<int> jakie, jakie2;

for(int i=0;i<n;i++){
    if(czy[i]){
        jakie.push_back(i);
    }
    else{
        jakie2.push_back(i);
    }
}

int maxi = -LLONG_MAX;

sort(jakie.begin(), jakie.end(), [&](auto a, auto b){
    return ile[a] > ile[b];
});

vector<int> pref2(jakie.size()+1, 0);
vector<int> v2(jakie.size()*m+1, -LLONG_MAX);
v2[0] = 0;

int i = 0;

for(int x : jakie){
    pref2[i+1] = pref2[i]+ile[x];
    i ++;
}
for(int i=1;i<=jakie.size();i++){
    v2[i*m] = pref2[i];
}

for(int i=1;i<m;i++){
    vector<int> suf(jakie.size()+1, -LLONG_MAX);
    vector<int> pref3(jakie.size(), -LLONG_MAX);

    for(int j=jakie.size()-1;j>=0;j--){
        suf[j] = max(suf[j+1], pref[jakie[j]][i-1]);
        /// cout<<i<<' '<<j<<' '<<suf[j]<<'\n';
    }
    if(!jakie.empty()){
        pref3[0] = pref[jakie[0]][i-1]-ile[jakie[0]];
        for(int j=1;j<jakie.size();j++){
            pref3[j] = max(pref3[j-1], pref[jakie[j]][i-1]-ile[jakie[j]]);
        }
    }
    for(int j=0;j<jakie.size();j++){
        v2[i+m*j] = max(pref2[j]+suf[j+1], pref2[j+1]+pref3[j]);
    }
}

vector<int> v3(jakie2.size()*m+1, -LLONG_MAX);
v3[0] = 0;

priority_queue<pair<int, pair<int, int>>> q;
for(int x : jakie2){
    q.push({v[x][0], {x, 0}});
}

int ile2 = 0;
int j = 1;

while(!q.empty()){
    auto [w, t] = q.top();
    auto [idx, i] = t;
    /// cout<<w<<' '<<idx<<' '<<i<<"<-- tu\n";
    q.pop();

    ile2 += w;
    v3[j++] = ile2;
    i ++;
    if(i < m){
        q.push({v[idx][i], {idx, i}});
    }
}

int wynik = -LLONG_MAX;
int l = max(0ll, k-(int)jakie2.size()*m);
int p = min(k, (int)jakie.size()*m);

for(int i=l;i<=p;i++){
    if(i <= jakie.size()*m && k-i <= jakie2.size()*m){
        wynik = max(wynik, v2[i]+v3[k-i]);
        /// cout<<wynik<<'\n';
    }
}

cout<<wynik;

}