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
#include <algorithm>
#include <iostream>
#include <vector>

// #include "testerka.h"

#define lol long long

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<lol>> norm, obru;
    for (int i = 0; i < n; i++) {
        vector<lol> vtemp(m + 1);
        vtemp[0] = 0;
        for (int j = 1; j < m + 1; j++) {
            lol tmp;
            cin >> vtemp[j];
            vtemp[j] += vtemp[j - 1];
        }
        if (vtemp[1] <= vtemp.rbegin()[0] - vtemp.rbegin()[1])
            norm.push_back(std::move(vtemp));
        else
            obru.push_back(std::move(vtemp));
    }

    // DP dla nieobroconych ("norm")
    vector<lol> DP_norm(norm.size() * m, 0);  // sumaryczna liczba nalesnikow
    if (norm.size()) {
        // sortujemy od najwiekszych do najmniejszych
        sort(norm.begin(), norm.end(), [](const vector<lol>& a, const vector<lol>& b) { return a.back() > b.back(); });
        for (int i = 1; i < norm.size(); i++) {  // wypelniamy pelnymi stosami
            lol v = DP_norm[(i - 1) * m] + norm[i - 1].back();
            for (int j = 0; j < m; j++) DP_norm[i * m + j] = v;
        }
        for (int i = 0; i < m; i++) {
            // ile minimalnie tracimy jezeli zjemy tylko $i nalesnikow na tym lub wiekszym stosie
            vector<lol> pref_podmiany(norm.size());
            pref_podmiany[0] = INT64_MIN;
            // niemozemy dobrac z pelnego stosu, jezeli mamy 0 pelnych stosow
            for (int j = 1; j < norm.size(); j++)
                pref_podmiany[j] = max(pref_podmiany[j - 1], norm[j - 1][i] - norm[j - 1].back());

            // ile maksymalnie zyskujemy jezeli dodajemy $i nalesnikow z tego lub mniejszego stosu
            vector<lol> pref_dobrania(norm.size());
            pref_dobrania[norm.size() - 1] = norm.back()[i];
            for (int j = norm.size() - 2; j >= 0; j--) pref_dobrania[j] = max(pref_dobrania[j + 1], norm[j][i]);

            // sprawdzamy co sie bardziej oplaca
            for (int j = 0; j < norm.size(); j++) {
                DP_norm[j * m + i] += max(pref_dobrania[j], pref_podmiany[j]+norm[j][i]);
            }
        }
    }
    DP_norm.push_back(0);
    for (auto i : norm) DP_norm.back() += i.back();

    // DP dla obruconych ("obru")
    vector<lol> DP_obru(1, 0);
    for (auto i : obru)
        for (int j = 1; j < m + 1; j++) DP_obru.push_back(i[j] - i[j - 1]);
    // sortujemy od najwiekszych do najmniejszych
    sort(DP_obru.begin() + 1, DP_obru.end(), [](lol a, lol b) { return a > b; });
    for (int i = 1; i < DP_obru.size(); i++) DP_obru[i] += DP_obru[i - 1];

    // Laczymy DP, znajdujac optymalne rozwiazanie dla k
    lol res = 0;
    for (int i = max(0, k - int(DP_obru.size()) + 1); i <= min(k, int(DP_norm.size() - 1)); i++)  //
        res = max(res, DP_norm[i] + DP_obru[k - i]);
    cout << res;

    return 0;
}