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

using namespace std;

struct StackSum {
    int value;
    int stack_nr;

    StackSum(int _value, int _stack_nr) : value(_value), stack_nr(_stack_nr) {}
};

int main() 
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, k;
    int value;

    cin >> n >> m >> k;

    vector<vector<int>> stacks(n);
    vector<StackSum*> stack_sums(n);
    vector<int> stack_positons_after_sort(n);

    // Read input
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> value;
            stacks[i].push_back(value);
        }
    }

    // Calculate prefix sums
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {
            stacks[i][j] += stacks[i][j - 1];
        }
    }

    // Prepare stack sums
    for (int i = 0; i < n; i++) {
        StackSum* stack_sum = new StackSum(stacks[i][m - 1], i);
        stack_sums[i] = stack_sum;
    }

    // Sort stack sums
    sort(stack_sums.begin(), stack_sums.end(), [](StackSum* a, StackSum* b) {
        return a->value > b->value;
    });

    // Positions after sorting
    for (int i = 0; i < n; i++) {
        stack_positons_after_sort[stack_sums[i]->stack_nr] = i;
    }

    // Building solution
    int entire_stacks = k / m;
    int rest = k % m;

    // Case 1 - entire stacks are enough. Take with biggest values.
    // Case 2 - try all combinations of 'rest' prefix sums and entire_stack - 1 biggest stacks.
    int sum = 0;
    for (int i = 0; i < entire_stacks; i++) {
        sum += stack_sums[i]->value;
    }

    if (rest == 0) {        
        cout << sum << endl;
    } else {
        int max_value = 0;
        for (int i = 0; i < n; i++) {
            int ith_prefix = stacks[i][rest - 1];
            int ith_stack_sum = stacks[i][m - 1];
            int current_value = 0;
            if (stack_positons_after_sort[i] < entire_stacks) {
                current_value = sum - ith_stack_sum + ith_prefix + stack_sums[entire_stacks]->value;
            } else {
                current_value = sum + ith_prefix;                
            }
            if (current_value > max_value) {
                max_value = current_value;
            }
        }
        cout << max_value << endl;
    }

    return 0;
}