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
#include<bits/stdc++.h>
using namespace std;
void smok(int L,int R,vector<long long> d,int m,int k,const vector<long long>&v_ile,const vector<vector<long long>>& abc,long long& res){
    if (L==R){
        for (int a=0;a<=k;a+=m){
            for (int b=0;b<=m &&a+b<=k;++b) {
                int rem=min((int)v_ile.size()-1,k-a-b);
                res=max(res,d[a]+abc[L][b]+v_ile[rem]);
            }}
        return;}
    int mid =(L+R)/2;
    vector<long long>dL=d,dR=d;
    for (int i=mid+1;i<=R;++i)
        for (int j=k;j>=m;--j)dL[j]=max(dL[j],dL[j - m]+abc[i][m]);
    smok(L,mid,dL,m,k,v_ile,abc,res);
    for (int i =L;i<=mid;++i)
        for (int j=k;j>=m;--j)dR[j]=max(dR[j],dR[j-m]+abc[i][m]);
    smok(mid+1,R,dR,m,k,v_ile,abc,res);}
int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    int n,m,k;cin>>n>>m>>k;
    vector<long long>v;
    vector<vector<long long>>abc;
    
    
    long long last=0;
    for (int i=0;i<n;++i) {
        vector<long long>p(m+1,0);
        bool rosnacy=true;
        for (int j=0;j<m;++j) {
            long long x;cin>>x;
            p[j+1]=p[j]+x;
            if (j>0&& x<last)rosnacy=false;
            last = x;}
        last=0;
        if (!rosnacy)for(int j=1;j<=m;++j)v.push_back(p[j]-p[j-1]);
        else abc.push_back(p);}
    sort(v.rbegin(),v.rend());
    vector<long long>v_ile(v.size()+1,0);
    for (int i=0;i<v.size();++i)v_ile[i+1]=v_ile[i]+v[i];
    long long res=0;
    if (abc.empty())res=v_ile[min((int)v.size(),k)];
    else {
        vector<long long>d(k+1,0);
        smok(0,abc.size()-1,d,m,k,v_ile,abc,res);
    }
    cout<<res;
    return 0;
}