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
128
129
130
131
132
133
134
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<vector<LL>> normal;
    vector<LL> inverted;

    for (int i = 0; i < n; ++i)
    {
        vector<LL> a(m);

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

        if (a[0] >= a[m - 1])
        {
            for (int j = 0; j < m; ++j)
            {
                inverted.push_back(a[j]);
            }
        }
        else
        {
            for (int j = 1; j < m; ++j)
            {
                a[j] += a[j - 1];
            }

            normal.push_back(a);
        }
    }

    sort(inverted.begin(), inverted.end(), greater<LL>());
    sort(normal.begin(), normal.end(), [](const vector<LL>& a, const vector<LL>& b) { return a.back() > b.back(); });

    int invertedCnt = inverted.size();
    int normalCnt = normal.size();
    int normalCntAll = n * m - invertedCnt;

    for (int i = 1; i < invertedCnt; ++i)
    {
        inverted[i] += inverted[i - 1];
    }

    vector<int> lg(normalCnt + 1);

    for (int i = 2; i <= normalCnt; ++i)
    {
        lg[i] = lg[i / 2] + 1;
    }

    vector<LL> sums(normalCnt + 1);

    for (int i = 0; i < normalCnt; ++i)
    {
        sums[i + 1] = sums[i] + normal[i].back();
    }

    int logs = lg[normalCnt];

    vector<vector<vector<LL>>> rangeMax(m - 1, vector<vector<LL>>(logs + 1, vector<LL>(normalCnt)));
    vector<vector<vector<LL>>> rangeMin(m - 1, vector<vector<LL>>(logs + 1, vector<LL>(normalCnt)));

    for (int mi = 0; mi < m - 1; ++mi)
    {
        for (int i = 0; i < normalCnt; ++i)
        {
            rangeMax[mi][0][i] = normal[i][mi];
            rangeMin[mi][0][i] = normal[i].back() - normal[i][mi];
        }

        for (int i = 1; i <= logs; ++i)
        {
            for (int j = 0; j + (1 << i) <= normalCnt; ++j)
            {
                rangeMax[mi][i][j] = max(rangeMax[mi][i - 1][j], rangeMax[mi][i - 1][j + (1 << (i - 1))]);
                rangeMin[mi][i][j] = min(rangeMin[mi][i - 1][j], rangeMin[mi][i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    LL res = 0;

    for (int i = max(0, k - normalCntAll); i <= min(k, invertedCnt); ++i)
    {
        LL tmp = 0;

        if (i > 0)
            tmp += inverted[i - 1];

        int left = k - i;

        if (left > 0)
        {
            int full = left / m;
            int part = left % m;

            LL tmp2 = sums[full];

            if (part > 0)
            {
                int l = lg[normalCnt - full];

                tmp2 += max(rangeMax[part - 1][l][full], rangeMax[part - 1][l][normalCnt - (1 << l)]);

                l = lg[full + 1];

                tmp2 = max(tmp2, sums[full + 1] - min(rangeMin[part - 1][l][0], rangeMin[part - 1][l][full - (1 << l) + 1]));
            }

            tmp += tmp2;
        }

        res = max(res, tmp);
    }

    cout << res << "\n";

    return 0;
}