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
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

int main () {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	vector<vector<int64_t> > nal(n, vector<int64_t>(m, 0));
	vector<vector<int64_t> > prefixes(n, vector<int64_t>(m + 1, 0));
	vector<vector<int64_t> > suffixes(n, vector<int64_t>(m + 1, 0));
	priority_queue<pair<int64_t, pair<int, int> > > q;
	vector<int> asc_rows;
	vector<int64_t> sums(n, 0);
	int64_t total_asc_sum = 0;
	int asc_rows_cnt = 0;
	int desc_rows_cnt = 0;
	for (int i = 0; i < n; ++i) {
		prefixes[i][0] = 0;
		for (int j = 0; j < m; ++j) {
			scanf("%lld", &nal[i][j]);
			sums[i] += nal[i][j];
			prefixes[i][j + 1] = prefixes[i][j] + nal[i][j];
		}
		suffixes[i][0] = 0;
		for (int j = 0; j < m; ++j) {
			suffixes[i][j + 1] = suffixes[i][j] + nal[i][m - 1 - j];
		}
		if (nal[i][0] >= nal[i][m - 1]) {
			q.push(make_pair(nal[i][0], make_pair(i, 0)));
			++desc_rows_cnt;
		}
		else {
			asc_rows.push_back(i);
			++asc_rows_cnt;
			total_asc_sum += sums[i];
		}
	}
	vector<int64_t> pdesc;
	pdesc.push_back(0);
	while (!q.empty()) {
		pair<int64_t, pair<int, int> > item = q.top();
		q.pop();
		pdesc.push_back(*pdesc.rbegin() + item.first);
		if (item.second.second < m - 1) {
			q.push(make_pair(nal[item.second.first][item.second.second + 1], make_pair(item.second.first, item.second.second + 1)));
		}
	}
	vector<pair<int64_t, int> > full_asc_rows;
	for (vector<int>::iterator it = asc_rows.begin(); it != asc_rows.end(); it++) {
		full_asc_rows.push_back(make_pair(-sums[*it], *it));
	}
	sort(full_asc_rows.begin(), full_asc_rows.end());
	vector<int64_t> pfull(1, 0);
	for (vector<pair<int64_t, int> >::iterator it = full_asc_rows.begin(); it != full_asc_rows.end(); it++) {
		pfull.push_back(*pfull.rbegin() - it->first);
	}
	vector<multiset<int64_t> > prefixes_after(m, multiset<int64_t>()), suffixes_before(m + 1, multiset<int64_t>());
	for (vector<int>::iterator it = asc_rows.begin(); it != asc_rows.end(); it++) {
		for (int j = 0; j < m; ++j) {
			prefixes_after[j].insert(prefixes[*it][j]);
		}
	}
	vector<int64_t> asc_max(min(k + 1, asc_rows_cnt * m) + 1, 0);
	for (int i = 0; i <= min(k + 1, asc_rows_cnt * m); ++i) {
		int full = i / m;
		int pref = i % m;
		if (pref) {
			suffixes_before[m - pref].insert(suffixes[full_asc_rows[full].second][m - pref]);
			asc_max[i] = max(pfull[full] + *prefixes_after[pref].rbegin(), pfull[full + 1] - *suffixes_before[m - pref].begin());
			prefixes_after[pref].erase(prefixes_after[pref].find(prefixes[full_asc_rows[full].second][pref]));
		}
		else {
			asc_max[i] = pfull[full];
		}
	}
	int64_t best = 0;
	for (int x = max(0, k - m * desc_rows_cnt); x <= min(k, m * asc_rows_cnt); ++x) {
		best = max(best, (desc_rows_cnt ? pdesc[k - x] : 0) + (asc_rows_cnt ? asc_max[x] : 0));
	}
	printf("%lld\n", best);
	return 0;
}