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
141
142
143
144
145
146
147
148
149
150
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

int main(){
	int n, m, k;

	std::cin >> n;
	std::cin >> m;
	std::cin >> k;

	std::vector<std::vector<long long>> stosyNalesnikow(n,std::vector<long long>(m));

	long long tempN;
	for (int i = 0; i < n; i++) { //dla i-tego stosu nalesnikow
		for (int j = 0; j < m; j++) { //dla j-tego nalesnika na danym stosie
			std::cin >> tempN;
			stosyNalesnikow[i][j] = tempN; //pobierz "wielkosc" nalesnika
		}
	}

	//ALG:
	//szukamy stosu malejacego (?) jezeli taki jest - heurystyka wyboru
	//zaczynamy od "konca" stosu (glebokosci maxSumIter) wybieramy najwiekszy
	//	jezeli jest remis dla ktoregokolwiek to musimy isc do gory o jeden i znowu porownac nizsza sume czy jest remis, itd az do samego poczatku
	//wybrany stos caly zjadamy
	//jezeli nadal nie wypelnilismy k to z reszty szukamy kolejnego stosu z nisza suma czesciowa i probujemy go zjesc az wypelnimy k


	//sumy czesciowe per kazdy poziom w stosie do m
	int maxSumIter = k > m ? m : k;
	std::vector<std::vector<long long>> sumyCzesciowe(n,std::vector<long long>(maxSumIter,0));

	//wypelnianie sum czesciowych per kazdy poziom glebokosci do maxSumIter
	for (int i = 0; i < n; i++) { //dla n stosow nalesnikow
		long long acc = 0;
		for (int j = 0; j < maxSumIter; j++) { //dodaj sumy nalesnikow
			acc += stosyNalesnikow[i][j];
			sumyCzesciowe[i][j] = acc;
		}
	}

	long long eatenCounter = 0;
	long long maxSum = 0;
	std::vector<int> chosenCounter;
	
	//najpierw sprobuj zjesc tylko jeden stos odpowiednio w glab
	//dla i = maxSumIter - base optimistic case
	for (int j = 0; j < n; j++) {
		if (sumyCzesciowe[j][maxSumIter-1] > maxSum) {
			chosenCounter.clear();
			maxSum = sumyCzesciowe[j][maxSumIter-1];
			chosenCounter.push_back(j);
		}
		else if (sumyCzesciowe[j][maxSumIter-1] == maxSum) {
			chosenCounter.push_back(j);
		}
	}

	if (chosenCounter.size() > 1) {
		for (int i = maxSumIter-2; i >= 0; i--) { //dla kazdegj sumy czesciowej - sprawdzanie glebokosci stosu do maxSumIter
			maxSum = 0;

			std::vector<int> newChosenCounter;

			for (auto it = chosenCounter.begin(); it != chosenCounter.end(); it++) {
				if (sumyCzesciowe[*it][i] > maxSum) {
					newChosenCounter.clear();
					maxSum = sumyCzesciowe[*it][i];
					newChosenCounter.push_back(*it);
				}
				else if (sumyCzesciowe[*it][i] == maxSum) {
					newChosenCounter.push_back(*it);
				}
			}

			if (newChosenCounter.size() == 1) break;
			else if (newChosenCounter.size() == 0) break;

			chosenCounter.clear();
			chosenCounter = newChosenCounter;
			newChosenCounter.clear();
		}
	}

	//zjadamy caly stos
	int chosenStack = chosenCounter[0];
	eatenCounter = sumyCzesciowe[chosenStack][maxSumIter - 1];
	chosenCounter.clear();

	if (maxSumIter == k) {
		std::cout << eatenCounter;
		return 0;
	}

	//jezeli nadal mozna zjesc nalesniki to probujemy jesc z dalszych stosow
	
	for (int currDiff = k - maxSumIter; currDiff > 0; currDiff -= maxSumIter) {
		int upperBound = currDiff / (float)maxSumIter > 1.0 ? maxSumIter : currDiff;
		maxSum = 0;

		for (int j = 0; j < n; j++) {
			if (sumyCzesciowe[j][upperBound - 1] > maxSum) {
				chosenCounter.clear();
				maxSum = sumyCzesciowe[j][upperBound - 1];
				chosenCounter.push_back(j);
			}
			else if (sumyCzesciowe[j][upperBound - 1] == maxSum) {
				chosenCounter.push_back(j);
			}
		}

		if (chosenCounter.size() > 1) {
			for (int i = upperBound - 2; i >= 0; i--) { //dla kazdegj sumy czesciowej - sprawdzanie glebokosci stosu do maxSumIter
				maxSum = 0;

				std::vector<int> newChosenCounter;

				for (auto it = chosenCounter.begin(); it != chosenCounter.end(); it++) {
					if (sumyCzesciowe[*it][i] > maxSum) {
						newChosenCounter.clear();
						maxSum = sumyCzesciowe[*it][i];
						newChosenCounter.push_back(*it);
					}
					else if (sumyCzesciowe[*it][i] == maxSum) {
						newChosenCounter.push_back(*it);
					}
				}

				if (newChosenCounter.size() == 1) break;
				else if (newChosenCounter.size() == 0) break;

				chosenCounter.clear();
				chosenCounter = newChosenCounter;
				newChosenCounter.clear();
			}
		}

		//zjadamy caly stos
		int chosenStack = chosenCounter[0];
		eatenCounter += sumyCzesciowe[chosenStack][currDiff - 1];
		chosenCounter.clear();

	}
	
	std::cout << eatenCounter;
	return 0;
}