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

using namespace std;

typedef uint64_t u64;

int main() {
    int n, m, k;
    (void)scanf("%d %d %d", &n, &m, &k);

    vector<uint64_t> singles;
    vector<vector<uint64_t>> multi;

    for(int i = 0; i < n; ++i){
        vector<uint64_t> row(m);
        for(int j = 0; j < m; ++j){
            (void)scanf("%llu", &row[j]);
        }

        if(row[0] >= row[m-1]){
            for(uint64_t x : row){
                singles.push_back(x);
            }
        }
        else{
            multi.emplace_back(row);
        }
    }

    sort(singles.begin(), singles.end(), greater<uint64_t>());
    vector<uint64_t> s_pref(singles.size() + 1, 0);
    for(int i = 0; i < (int)singles.size(); ++i){
        s_pref[i+1] = s_pref[i] + singles[i];
    }

    int num_m = multi.size();

    vector<vector<uint64_t>> dp_l(num_m + 2, vector<uint64_t>(k + 1, 0));
    vector<vector<uint64_t>> dp_r(num_m + 2, vector<uint64_t>(k + 1, 0));

    auto fill_dp = [&](vector<vector<uint64_t>>& dp, const vector<vector<uint64_t>>& source, bool reverse_order) {
        for(int i = 1; i <= num_m; ++i){
            int idx = reverse_order ? num_m - i : i - 1;
            uint64_t cum_sum = 0;
            for(uint64_t x : source[idx]){
                cum_sum += x;
            }

            for(int j = 0; j <= k; ++j){
                dp[i][j] = dp[i-1][j];
                if(j >= m){
                    dp[i][j] = max(dp[i][j], dp[i-1][j-m] + cum_sum);
                }
            }
        }
    };

    fill_dp(dp_l, multi, false);
    fill_dp(dp_r, multi, true);

    uint64_t max_pancakes = 0;

    for(int j = 0; j <= k; ++j){
        int s_picks = min((int)singles.size(), k - j);
        max_pancakes = max(max_pancakes, dp_l[num_m][j] + s_pref[s_picks]);
    }

    for(int i = 0; i < num_m; ++i){
        uint64_t partial_sum = 0;
        for(int x = 1; x < m && x <= k; ++x){
            partial_sum += multi[i][x-1];
            for(int left_cap = 0; left_cap <= (k - x); ++left_cap){
                int right_cap = (k - x) - left_cap;
            }
        }
    }

    printf("%llu\n", max_pancakes);
    fflush(stdout);
    return 0;
}