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
#include<iostream>
#include<vector>
#include<algorithm>
#define PB push_back
#define F first
#define S second
#define ll long long
using namespace std;
constexpr int MN=3e5+7;
vector<ll>stos[MN];
ll suma[MN];
ll mpref[MN];
ll pref[MN];
vector<ll>megastos;
vector<ll>akt;
vector<pair<ll,ll>>gomornicy;
bool comp2(pair<ll,ll>a,pair<ll,ll>b){if(a.F==b.F) return b.S>a.S; return b.F>a.F;}
bool comp(ll a,ll b){return a>b;}

int main(){
ios_base::sync_with_stdio(0);
int n,m,k;
ll a,b;
cin>>n>>m>>k;
int t=0;
for(int z=0;z<n;z++)
{
    akt.clear();
    for(int j=0;j<m;j++){cin>>a;akt.PB(a);}
    bool v=0;
    for(int j=0;j<m-1;j++)if(akt[j]<akt[j+1]){v=1;break;}
    if(!v){for(ll x:akt) megastos.PB(x);}
    else{stos[t]=akt;for(int j=0;j<m;j++) suma[t]+=akt[j];t++;}
}
sort(megastos.begin(),megastos.end(),comp);
for(int j=0;j<megastos.size();j++) mpref[j+1]=mpref[j]+megastos[j];

/*cout<<t<<endl;
for(int j=0;j<t;j++) cout<<suma[j]<<' ';cout<<endl;
cout<<megastos.size()<<endl;
for(int j=0;j<=megastos.size();j++) cout<<mpref[j]<<' ';cout<<endl;*/
ll ma=0;

for(int r=0;r<min(k+1,m);r++)
{
    ll wynik=0;
    int dopelnienie=(k-r)%m;
    int ile=(k-r)/m;
    if(megastos.size()<dopelnienie) continue;

    wynik+=mpref[dopelnienie];

   for(int j=dopelnienie;j+m-1<megastos.size();j+=m){gomornicy.PB({mpref[j+m]-mpref[j],0});}
   for(int j=0;j<t;j++){gomornicy.PB({suma[j],pref[j]});pref[j]+=stos[j][r];}
   sort(gomornicy.begin(),gomornicy.end(),comp2);

   for(int j=0;j<ile;j++)wynik+=gomornicy[j].F;
   if(gomornicy.size()<=ile)ma=max(ma,wynik);
   else{
        wynik+=gomornicy[ile].F;
   for(int j=0;j<=ile;j++){ma=max(ma,wynik-gomornicy[j].F+gomornicy[j].S);}
   wynik-=gomornicy[ile].F;
   for(int j=ile+1;j<gomornicy.size();j++){ma=max(ma,wynik+gomornicy[j].S);}
   }
}
cout<<ma<<endl;
}