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

using namespace std;

using ll = long long;

ll n, m, k;
ll one_size;
std::vector<ll> best_cost_one, one_sum_pref;
ll k_size;
std::vector<pair<ll, ll>> best_cost_k;
std::vector<ll> k_sum_pref;
std::vector<ll> k_rank, k_sums;
std::vector<std::vector<ll>> k_stacks;

ll convert_index(ll index, ll blocked) {
	if (index >= blocked) {
		return index + 1;
	}
	return index;
}

ll try_solution(ll base_score, ll avalible, ll blocked, ll sum) {
	// std::cerr << base_score << " " << avalible << " " << blocked << " " << sum << endl;

	bool is_blocked = blocked <= k_size;
	ll greed = min(avalible % m, one_size);
	avalible = avalible / m;
	ll max_one = min((one_size - greed) / m, avalible);
	ll max_k = k_size - is_blocked;
	ll start = max(0LL, avalible - max_k), end = max_one + 1, mid;
	// println(cerr, "greed:{} m:{}", greed, m);
	// println(cerr, "s:{} e:{}", start, end);
	while(start + 1 < end) {
		mid = (start + end) / 2;
		// println(cerr, "s:{} e:{} m:{}", start, end, mid);
		if (mid > 0 
			&& mid > avalible - max_k 
			&& one_sum_pref[greed + mid * m] - one_sum_pref[greed + (mid - 1) * m] < best_cost_k[convert_index(avalible - mid + 1, blocked)].first) {
			end = mid;
		} else if (mid < max_one 
			&& one_sum_pref[greed + (mid + 1) * m] - one_sum_pref[greed + mid * m] > best_cost_k[convert_index(avalible - mid, blocked)].first) {
			start = mid;
		} else {
			start = mid;
			end = mid + 1;
		}
	}
	// println(cerr, "found:{} avalible:{}", start, avalible);
	ll score = base_score;
	// println(cerr, "one_sum_part:{}", one_sum_pref[greed + start * m]);
	score += one_sum_pref[greed + start * m];
	// println(cerr, "index:{} k_sum_part:{}",convert_index(min(avalible - start, max_k), blocked), k_sum_pref[convert_index(min(avalible - start, max_k), blocked)]);
	score += k_sum_pref[convert_index(min(avalible - start, max_k), blocked)];
	// if (blocked <= k_size) {
		// println(cerr, "k_rank_blocked:{}", blocked);
	// }
	if (blocked <= k_size && convert_index(min(avalible - start, max_k), blocked) > blocked) {
		// println(cerr, "reduced by:{}", k_sums[blocked]);
		score -= sum;
	}
	// println(cerr, "score:{}", score);
	return  score;
}

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

	cin >> n >> m >> k;

	std::vector<ll> stack;
	stack.resize(m);
	best_cost_one.push_back(0);
	best_cost_k.push_back({0, -1});
	k_stacks.push_back({});
	k_sums.push_back({0});
	ll sum = 0;

	k_size = 0;

	for(int i = 0; i < n; i++) {
		sum = 0;

		for(int j = 0; j < m; j++) {
			cin >> stack[j];
			sum += stack[j];
		}

		if (stack.front() >= stack.back()) {
			for(auto& el: stack) {
				best_cost_one.push_back(el);
			}
		} else {
			best_cost_k.push_back({sum, k_size + 1});	
			k_sums.push_back(sum);
			k_stacks.push_back(stack);
			k_size++;
		}
	}
	one_size = best_cost_one.size() - 1;
	for(int i = 0; i < 2 * m; i++) {
		one_size++;
		best_cost_one.push_back(0);
	}

	sort(best_cost_one.begin() + 1, best_cost_one.end(), std::greater<>());
	sort(best_cost_k.begin() + 1, best_cost_k.end(), std::greater<>());

	// cout << "After sorting" << endl;

	one_sum_pref.resize(one_size + 1);
	for(int i = 1; i <= one_size; i++) {
		one_sum_pref[i] = one_sum_pref[i - 1] + best_cost_one[i];
	}
	k_rank.resize(k_size + 1);
	k_sum_pref.resize(k_size + 1);
	for(int i = 1; i <= k_size; i++) {
		k_sum_pref[i] = k_sum_pref[i - 1] + best_cost_k[i].first;
		k_rank[best_cost_k[i].second] = i;
	}

	// cout << "After setup" << endl;
	// println(cerr, "ks:{} os:{}", k_size, one_size);

	ll res = try_solution(0, k, n * m + 1, 0);
	for(int i = 1; i <= k_size; i++) {
		ll sum = 0;
		for(int j = 1; j < m && j <= k; j++) {
			sum += k_stacks[i][j - 1]; 
			res = max(res, try_solution(sum, k - j, k_rank[i], k_sums[i]));
		}
	}

	cout << res;
}