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
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
constexpr int N = 3e5 + 5;

int n, m, k, cnt = 0, s[N], ind[N], dl, r;
ll v[N], p[N], sum[N], val[N], ans = 0;
vector<vector<ll>> a, pr;
bool used[N];

bool comp1(const int& x, const int& y) {
    if(a[x][0] >= a[x][m - 1]) return false;
    if(a[y][0] >= a[y][m - 1]) return true;
    return sum[x] >= sum[y];
}

bool comp2(const int& x, const int& y) {
    return pr[x][r] >= pr[y][r];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    a.resize(n, vector<ll>(m));
    pr.resize(n, vector<ll>(m + 1));
    for(int i = 0; i < n; ++i) {
        sum[i] = 0;
        for(int j = 0; j < m; ++j) {
            cin >> a[i][j];
            sum[i] += a[i][j];
        }
    }
    for(int i = 0; i < n; ++i) {
        if(a[i][0] >= a[i][m - 1]) {
            for(int j = 0; j < m; ++j) {
                v[cnt * m + j] = a[i][j];
            }
            ++cnt;
        }
    }
    dl = n - cnt;
    sort(v, v + cnt * m, greater<>());
    p[0] = 0;
    for(int i = 1; i <= cnt * m; ++i) p[i] = p[i - 1] + v[i - 1];
    // V type taken care of
    for(int i = 0; i < n; ++i) s[i] = i;
    sort(s, s + n, comp1);
    for(int i = 0; i < dl; ++i) ind[i] = s[i];
    for(int i = 0; i < n; ++i) {
        pr[i][0] = 0;
        for(int j = 1; j <= m; ++j) {
            pr[i][j] = pr[i][j - 1] + a[i][j - 1];
        }
    }
    // cerr << "---------------" << '\n';
    // for(int i = 0; i < n; ++i) {
    //     for(int j = 0; j < m; ++j) {
    //         cerr << pr[i][j] << " ";
    //     }
    //     cerr << '\n';
    // }
    // cerr << "---------------" << '\n';
    if(cnt * m >= k) ans = p[k];
    for(r = 1; r <= m; ++r) {
        if(r > k || r > dl * m) break;
        memset(used, 0, n * sizeof(bool));
        sort(ind, ind + dl, comp2);
        ll j = 0, c = 0;
        if(r <= k && k - r <= cnt * m) ans = max(ans, pr[ind[0]][r] + p[k - r]);
        ll sx = LLONG_MAX;
        // if(ans == 545) cout << r << "XDDDD\n";
        // if(ans == 545) return 0;
        for(int i = 0; i < dl - 1; ++i) {
            int num = r + (i + 1) * m;
            if(num > k || num > dl * m) break;
            used[s[i]] = 1;
            c += sum[s[i]];
            while(used[ind[j]]) ++j;
            sx = min(sx, sum[s[i]] - pr[s[i]][r]);
            if(num <= k && k - num <= cnt * m) ans = max(ans, p[k - num] + max(c + pr[ind[j]][r], c + sum[s[i + 1]] - sx));
            // if(ans == 545) cout << c << " " << p[k - num] << '\n';
            // if(ans == 545) return 0;
        }
    }
    cout << ans << '\n';
}

/*
p[i] = v[0]+...+v[i - 1], where v are the ones upside down
cnt - number of plates upside down
dl - number of plates positioned normally
s[0...dl - 1] are the plates positioned normally sorted by size in decreasing order.
ind[0...dl - 1] are plates positioned normally sorted by the size of their prefix of length r.
pr[i][r] is the sum a[i][n - 1] + .. + a[i][n - r]
sx is the current minimum over a[i][0] + ... + a[i][n - r - 1] over the ones used
*/