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
#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int i,j;
    long long x;
    bool operator <(const Node &B)const
    {
        return x < B.x;
    }
};
int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<long long>>tab(n,vector<long long>(m));
    vector<pair<long long,int>>U1;
    vector<int>U2;
    vector<long long>W1={0},W2={0};
    for(int i=0;i<n;i++)
    {
        long long s=0;
        bool CzyRosnace=1;
        for(int j=0;j<m;j++)
        {
            cin>>tab[i][j];
            if(j>0&&tab[i][j-1]>tab[i][j]){CzyRosnace=0;}
            s+=tab[i][j];
        }
        if(CzyRosnace){U1.push_back({s,i});}
        else{U2.push_back(i);}
    }
    priority_queue<Node>Q;
    for(int u : U2)
    {
        Q.push({u,0,tab[u][0]});
    }
    long long suma;
    suma=0;
    while(!Q.empty())
    {
        Node temp=Q.top();
        Q.pop();
        long long x=temp.x;
        int i=temp.i,j=temp.j;
        suma+=x;
        W2.push_back(suma);
        if(j+1<m){Q.push({i,j+1,tab[i][j+1]});}
    }
    sort(U1.begin(),U1.end());
    reverse(U1.begin(),U1.end());
    vector<long long>Maxx1(m,-numeric_limits<long long>::max()/3);
    vector<vector<long long>>Maxx2(U1.size()+1,vector<long long>(m,-numeric_limits<long long>::max()/3));
    for(int i=(int)U1.size()-1;i>=0;i--)
    {
        const int ind=U1[i].second;
        long long s=0;
        for(int j=0;j<m;j++)
        {
            s+=tab[ind][j];
            Maxx2[i][j]=max(Maxx2[i+1][j],s);
        }
    }
    suma=0;
    for(int i=0;i<(int)U1.size();i++)
    {
        const int ind=U1[i].second;
        long long s=0;
        for(int j=0;j<m;j++)
        {
            s+=tab[ind][j];
            Maxx1[j]=max(Maxx1[j],s-U1[i].first);
            W1.push_back(suma+max(Maxx2[i][j],U1[i].first+Maxx1[j]));
        }
        suma+=U1[i].first;
    }
    long long wynik=0;
    for(int i=0;i<(int)W1.size();i++)
    {
        int i2=k-i;
        if(i2<0||i2>=(int)W2.size()){continue;}
        wynik=max(wynik,W1[i]+W2[i2]);
    }
    cout<<wynik<<'\n';
    return 0;
}