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

using int64_t = int64_t; // linux :(

int main(){
	using namespace std;
	ios::sync_with_stdio(false), cin.tie(nullptr);
			
	int n, m, k; // { stosy, po ile naleśników, ile można zjeść }
	cin >> n >> m >> k; 
	
	vector<vector<int64_t>> a(n, vector<int64_t> (m));
	
	vector<int64_t> dec;
	vector<vector<int64_t>> inc;
	vector<int64_t> sum_of_stos(n);
	vector<int> ids;
	
	for(int i = 0;i < n;i++){
		bool isDec = true;
		for(int j = 0;j < m;j++){
			cin >> a[i][j];
			if(j > 0) {
				isDec &= (a[i][j] <= a[i][j - 1]); // A[i][j-1] >= A[i][j]
			}
		}
		if(isDec){
			for(int j = 0;j < m;j++){
				dec.push_back(a[i][j]);
			}
		} else {
			ids.push_back(i);
			for(int j = 0;j < m;j++){
				sum_of_stos[i] += a[i][j];
			}
		}
	}
	
	sort(ids.begin(), ids.end(), [&](int i, int j){
		return sum_of_stos[i] > sum_of_stos[j];
	});
	
	for(int x : ids){
		inc.push_back(a[x]);
	}
	
	int decCount = (int)dec.size();
	int incCount = (int)inc.size() * m;
	
	int64_t ans = 0;
	
	sort(dec.rbegin(), dec.rend());
	for(int i = 1;i < decCount;i++){
		dec[i] += dec[i - 1];
	}
	
	int ileTab = incCount / m;
	vector<int64_t> prefS(ileTab + 1);
	vector<vector<int64_t>> ps(ileTab, vector<int64_t> (m));
	
	{
		for(int stos = 0;stos < ileTab;stos++){
			prefS[stos + 1] += prefS[stos];
			for(int j = 0;j < m;j++){
				ps[stos][j] += inc[stos][j];
				if(j) ps[stos][j] += ps[stos][j - 1];
				prefS[stos + 1] += inc[stos][j];
			}
		}
	}

	vector<vector<int64_t>> best_take(ileTab, vector<int64_t> (m)); 
	// best_take[i][j] -> the best you can take if you have taken the full first i-1
	// and know you can take j more
	// we have made observation that it's optimal to only take from one particular in this case.
	for(int stos = ileTab - 1;stos >= 0;stos--){
		int64_t sum = 0;
		for(int j = 0;j < m;j++){
			sum += inc[stos][j];
			// upd best_take[stos][j]
			best_take[stos][j] = sum;
			if(stos + 1 < ileTab){
				best_take[stos][j] = max(best_take[stos + 1][j], best_take[stos][j]);
			}
		}
	}

	// swsto einai kai ayto alla oxi optimal.
	for(int take_inc = 0;take_inc <= min(k, incCount);take_inc++){
		// we will take some (prefix of full) and one non-full (in this case its after the full ones)
		int take_full = take_inc / m;
		//~ if(take_inc % m > 0) {
			//~ assert(take_full < ileTab);
		//~ }

		int64_t sum_of_inc = prefS[take_full] + (take_inc % m > 0 ? best_take[take_full][take_inc % m - 1] : 0);
		int64_t sum_of_dec = (k - take_inc > 0 && k - take_inc <= decCount ? dec[k - take_inc - 1] : 0); // you could put min(decCount, k-take_inc) 
																																																		// but in the end we will get there because its suboptimal to take less than k
																																																		// + k <= n*m
		ans = max(ans, sum_of_inc + sum_of_dec);
	}
	
	vector<vector<int>> who(ileTab, vector<int> (m, 0)); // who to take, who is best
	
	auto Calc = [&](int index, int j) -> int64_t {
		// return sum from [j+1..m]
		j=max(j,0);
		return ps[index][m-1] - ps[index][j];
	};

	for(int stos = 1;stos < ileTab;stos++){
		int64_t me_sum = 0;
		for(int j = m-1;j >= 0;j--){
			who[stos][j] = who[stos - 1][j];
			if(me_sum < Calc(who[stos - 1][j], j)){ // for m-1 this is always 0 ?
				who[stos][j] = stos;
			}
			me_sum += inc[stos][j];
		}
	}
	
	for(int take_inc = 0;take_inc <= min(k, incCount);take_inc++){
		if(take_inc % m == 0) continue;
		int take_full = take_inc / m;
		if(take_inc % m > 0) {
			assert(take_full < ileTab);
		}
		
		int x = take_full;
		int y = take_inc % m - 1; // 0-indexed!!!!
		
		int64_t sum_of_inc = prefS[take_full + 1] - Calc(who[x][y], y);
		int64_t sum_of_dec = (k - take_inc > 0 && k - take_inc <= decCount ? dec[k - take_inc - 1] : 0);
		ans = max(ans, sum_of_inc + sum_of_dec);
	}
	
	cout << ans << '\n';
	
	return 0;
}