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 <bits/stdc++.h>
using namespace std;

vector<long long> good_pancakes;
vector<long long> good_sums;
vector<long long> evil_pancakes[300010];
vector<long long> prefix_sums[300010];
int evil_stacks = 0;

int eating;
long long result = 0;

void update_result(int pancakes_used, long long new_val) {
	if (eating - pancakes_used > good_pancakes.size() || eating - pancakes_used < 0) {
		return;
	}
	else {
		long long result0 = good_sums[eating - pancakes_used] + new_val;
		if (result0 > result) {
			result = result0;
		}
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);

	int stack_count, stack_size;

	cin >> stack_count >> stack_size >> eating;

	for (int i = 0; i < stack_count; i++) {
		bool is_good = true;
		vector<long long> new_pancakes = {};
		long long pancake;
		for (int j = 0; j < stack_size; j++) {
			cin >> pancake;
			new_pancakes.push_back(pancake);
			if (j >= 1) {
				if (new_pancakes[j - 1] < new_pancakes[j]) {
					is_good = false;
				}
			}
		}
		if (is_good) {
			good_pancakes.insert(good_pancakes.end(), new_pancakes.begin(), new_pancakes.end());
		}
		else {
			evil_pancakes[evil_stacks] = move(new_pancakes);
			evil_stacks++;
		}
	}

	sort(good_pancakes.begin(), good_pancakes.end());

	good_sums.reserve(good_pancakes.size() + 1);

	good_sums.push_back(0);
	long long last = 0;
	for (int i = good_pancakes.size() - 1; i >= 0; i--) {
		last += good_pancakes[i];
		good_sums.push_back(last);
	}
	// Taken care of the good pancake stacks

	// Sort pancake stacks, calculate their prefix sums
	vector<pair<long long, int>> sorted_stacks;
	sorted_stacks.reserve(evil_stacks);

	long long evil_stack_sum = 0;

	for (int i = 0; i < evil_stacks; i++) {
		long long sum = 0;
		prefix_sums[i].push_back(sum);
		for (int j = 0; j < stack_size; j++) {
			sum += evil_pancakes[i][j];

			// Calculate prefix sums
			prefix_sums[i].push_back(sum);
		}
		// Add a sum to be sorted
		sorted_stacks.push_back({-sum, i});

		// Update the total evil stack sum
		evil_stack_sum += sum;
	}
	sort(sorted_stacks.begin(), sorted_stacks.end());

	// Do the evil pancake stacks, assuming we choose a least bottom part from our best stacks
	for (int r = 1; r <= stack_size; r++) {
		// We first do options where we take r mod stack_size evil pancakes, and the rest good pancakes

		priority_queue<pair<long long, int>> best_stacks; // Will keep track of i+1 best stacks
		long long total_sum_of_q = 0;

		for (int i = 0; i < evil_stacks; i++) {
			// Consider how many full stacks we take

			int stack_to_add = sorted_stacks[i].second;
			long long b_value = prefix_sums[stack_to_add][stack_size] - prefix_sums[stack_to_add][r];
			best_stacks.push({-b_value, stack_to_add});
			total_sum_of_q += prefix_sums[stack_to_add][stack_size];

			long long local_result = total_sum_of_q + best_stacks.top().first;
			int pancakes_used = i * stack_size + r;
			update_result(pancakes_used, local_result);
		}
	}
	
	// Now do evil pancakes assuming we choose the largest top part from outside
	for (int r = 1; r <= stack_size; r++) {
		priority_queue<pair<long long, int>> worst_stacks; // Will keep track of i+1 worst stacks
		long long total_sum_of_q = evil_stack_sum;

		for (int i = 0; i < evil_stacks; i++) {
			// Consider how many empty stacks we discard
			// We will take one of them for its high top content

			int stack_to_discard = sorted_stacks[evil_stacks - 1 - i].second;
			long long a_value = prefix_sums[stack_to_discard][r];

			worst_stacks.push({a_value, stack_to_discard});
			total_sum_of_q -= prefix_sums[stack_to_discard][stack_size];

			long long local_result = total_sum_of_q + worst_stacks.top().first;
			int pancakes_used = (evil_stacks - i - 1) * stack_size + r;

			update_result(pancakes_used, local_result);
			// Is there any edge case? Maybe the above edge case gets covered here?
		}
	}

	// Both cases above skip the possibility of taking no evil pancakes
	update_result(0, 0);

	cout << result << "\n";

}