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

using namespace std;

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

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

    // cout << "start" << endl;

    vector<vector<long long>> stacks(n, vector<long long>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> stacks[i][j];
        }
    }
    if (n == 1) {
      long long total_sum = 0;

      for (int i = 0; i < k; i++) {
        total_sum += stacks[0][i];
      }
      cout << total_sum << endl;
      return 0;
    }

    vector<vector<long long>> normal_stacks;
    vector<long long> all_reversed_stacks;
    for (int i = 0; i < n; i++) {
        if (m > 1 && stacks[i][0] > stacks[i][m - 1]) {
            for (int j = 0; j < m; j++) {
                all_reversed_stacks.push_back(stacks[i][j]);
            }
        } else {
            normal_stacks.push_back(stacks[i]);
        }
    }

    sort(all_reversed_stacks.begin(), all_reversed_stacks.end(), greater<long long>());

    long long reversed_stack_sum = 0;
    long long max_total = 0;


    long long reversed_stack_sum_2 = 0;
    for (int i = 1; i < k+1; i++) {
          // cout << i - 1 << " " << all_reversed_stacks.size() << endl;
        if (i <= all_reversed_stacks.size()) {
            reversed_stack_sum_2 += all_reversed_stacks[i-1];
        } else {
            break;
        }
    }

    long long full_total = 0;
    vector<pair<long long, int>> normal_stacks_with_sum;
    for (int i = 0; i < normal_stacks.size(); i++) {
        long long current_sum = 0;
        for (int j = 0; j < m; j++) {
            current_sum += normal_stacks[i][j];
        }
        normal_stacks_with_sum.push_back({current_sum, i});
    }
    sort(normal_stacks_with_sum.begin(), normal_stacks_with_sum.end(), greater<pair<long long, int>>());

    vector<priority_queue<pair<long long, int>>> biggest_until_i(m);
    vector<long long> cum_sum_biggest_until_i(normal_stacks.size(), 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < normal_stacks.size(); j++) {
            cum_sum_biggest_until_i[j] += normal_stacks[j][i];
            biggest_until_i[i].push({cum_sum_biggest_until_i[j], j});
        }
    }
    set<int> used_stacks;
    vector<long long> smallest_until_i(m, 1e17);
    
    // for (int i = 0; i < k+1; i++) {
   

    //     if (i > 0 && i <= all_reversed_stacks.size()) {
    //         reversed_stack_sum += all_reversed_stacks[i-1];
    //     }

    //     if (normal_stacks.size() * m < k - i || all_reversed_stacks.size() < i) {
    //         continue;
    //     }
    //     max_total = max(max_total, reversed_stack_sum);
    // }
    
    for (int i = 0; i < k+1; i++) {
        if (i % m == 0 && i > 0 && normal_stacks.size() * m >= i) {
            full_total += normal_stacks_with_sum[i/m - 1].first;
            used_stacks.insert(normal_stacks_with_sum[i/m - 1].second);
            
            vector<long long> curr_stack = normal_stacks[normal_stacks_with_sum[i/m - 1].second];
            long long cum_sum = 0;
            for (int j = m-1; j > 0; j--) {
                cum_sum += curr_stack[j];
                smallest_until_i[j] = min(smallest_until_i[j], cum_sum);
            }
        }
        if (normal_stacks.size() * m < i || all_reversed_stacks.size() < k - i) {
            continue;
        }
        long long normal_sum = 0;
        if (i % m == 0) {
            normal_sum = full_total;
        } else {
            long long max_val = 0;
            while (!biggest_until_i[i%m-1].empty()) {
                if (used_stacks.find(biggest_until_i[i%m-1].top().second) == used_stacks.end()) {
                    max_val = biggest_until_i[i%m-1].top().first;
                    break;
                } else {
                    biggest_until_i[i%m-1].pop();
                }
            }
            if (normal_stacks_with_sum[i/m].first - smallest_until_i[i%m] > max_val) {
                normal_sum = full_total + normal_stacks_with_sum[i/m].first - smallest_until_i[i%m];
            } else {
                normal_sum = full_total + max_val;
            }
        }
        max_total = max(max_total, normal_sum + reversed_stack_sum_2);
        if (k - i > 0 && k - i <= all_reversed_stacks.size()) {
            reversed_stack_sum_2 -= all_reversed_stacks[k-i-1];
        }
    }
    cout << max_total << endl;

    return 0;
}