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
#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <climits>
using namespace std;

typedef vector<vector<int> > Bottles;

class SolverException
{};

class IncorrectInput
{};

class Solver
{
public:
	int Solve(int height, int neededBottles, const Bottles& bottles)
	{
		if (neededBottles > height * (height + 1) / 2)
			throw IncorrectInput();

		int answer = INT_MAX;
		for (int row = 1; row <= bottles.size(); ++row)
		{
			for (int column = 1; column <= bottles[row - 1].size(); ++column)
			{
				const int currentYear = bottles[row - 1][column - 1];
				if (getMinimalBottlesNeededToTakeToReachGivenBottle(row, column) <= neededBottles
					&& answer > currentYear)
				{
					answer = currentYear;
				}
			}
		}

		return answer;
	}
private:
	int getMinimalBottlesNeededToTakeToReachGivenBottle(int row, int column)
	{
		if (column > row || row < 1)
			throw SolverException();

		return column * (row - column + 1);
	}
};

Bottles CreateBottles(int numberOfElements, int* inputArray)
{
	Bottles result(1);
	int targetRow = 1;
	for (int currentElement = 0; currentElement < numberOfElements; ++currentElement)
	{
		
		if (result[targetRow - 1].size() >= targetRow)
			++targetRow;

		if (result.size() < targetRow)
			result.push_back(vector<int>());

		result[targetRow - 1].push_back(inputArray[currentElement]);
	}

	return result;
}

//#define DEBUG
int main()
{
	Solver solver;
	for (int year = 1; year <= 2019; ++year)
		assert(solver.Solve(1, 1, CreateBottles(1, new int[1] {year})) == year);

	assert(solver.Solve(5, 7, CreateBottles(15, new int[15]{ 1999, 2019, 2010, 850, 1500, 1600, 900, 900, 710, 900, 1000, 800, 600, 800, 1000 })) == 710);
#ifdef DEBUG
#endif

	int height, neededBottles, currentYear;
	scanf("%d %d", &height, &neededBottles);
	Bottles bottles(height);
	for (int row = 1; row <= height; ++row)
	{
		for (int number = 0; number < row; ++number)
		{
			scanf("%d", &currentYear);
			bottles[row - 1].push_back(currentYear);
		}
	}

	printf("%d\n", solver.Solve(height, neededBottles, bottles));

#ifdef DEBUG
	system("pause");
#endif
	return 0;
}