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
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    vector<vector<int>> ros,mal;
    vector<int> a(m);

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            cin>>a[j];

        if(a[0]<=a[m-1])
            ros.push_back(a);
        else
            mal.push_back(a);
    }

    int aW=mal.size();
    vector<int> w(aW*m+1);
    priority_queue<tuple<int,int,int>> q;

    for(int i=0; i<aW; i++)
        q.push({mal[i][0],i,0});

    int s=0;
    for(int i=1; i<w.size(); i++){
        auto [wart, id, p]=q.top();
        q.pop();

        s+=wart;
        w[i]=s;

        if(p+1<m)
            q.push({mal[id][p+1],id,p+1});
    }

    int bW=ros.size();
    vector<int> suma(bW);

    for(int i=0; i<bW; i++)
        for(int j=0; j<m; j++)
            suma[i]+=ros[i][j];

    vector<int> kolej(bW);
    for(int i=0;i<bW;i++)
        kolej[i]=i;

    sort(kolej.begin(),kolej.end(),[&](int a,int b)
    {
        return suma[a]>suma[b];
    });

    vector<vector<int>> ros2(bW);
    vector<int> suma2(bW);

    for(int i=0;i<bW;i++){
        ros2[i]=ros[kolej[i]];
        suma2[i]=suma[kolej[i]];
    }
    ros=ros2;
    suma=suma2;

    vector<int> pref(bW+1);
    for(int i=0; i<bW; i++)
        pref[i+1]=pref[i]+suma[i];

    vector<vector<int>> suf(bW+1, vector<int>(m+1));
    for(int i=bW-1; i>=0; i--)
    {
        int fergus=0;
        for(int x=1; x<=m; x++)
        {
            fergus+=ros[i][x-1];
            suf[i][x]=max(suf[i+1][x],fergus);
        }
    }

    vector<vector<int>> przegralem(bW+1,vector<int>(m+1, LLONG_MAX));
    for(int i=0; i<bW; i++)
    {
        int fergus=0;
        for(int x=1; x<=m; x++)
        {
            fergus+=ros[i][x-1];
            przegralem[i+1][x]=min(przegralem[i][x],suma[i]-fergus);
        }
    }

    int odp=0;
    for(int a=0; a<=min(k,aW*m); a++)
    {
        int r1 = k-a;
        if(r1 > bW*m)
            continue;

        int p=r1/m;
        int x=r1%m;

        if(x == 0)
            odp=max(odp, w[a]+pref[p]);
        else
            odp=max({odp, w[a]+pref[p]+suf[p][x], w[a]+pref[p+1]-przegralem[p+1][x]});
    }
    cout<<odp;
}