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
/* 2019-12-09 Jędrzej Pacanowski
 * PA2019 Wina */
#include <iostream>
#include <cmath>
#include <vector>
typedef unsigned short u16;
typedef unsigned int u32;

static inline constexpr u32 najwiekszy_wiersz(u16 kol, u32 do_sciagniecia){
	u32 _res = kol + std::ceil( (float)(do_sciagniecia - kol) / (float)(kol+1) );
	return _res - 1;
}

int main()
{
	std::cin.tie(0); std::ios_base::sync_with_stdio(false);
	u16 n; // ile rzędów [1 ; 2tys.]
	u32 k; // ile buletek [1; suma ciągu dla n]
	std::cin >> n >> k;
	
	std::vector<std::vector<u16>> piramida(n);
	for(u16 i=0; i<n; i++){
		piramida[i].reserve(i+1); // nr rzędu = i+1
		for(u16 j=0; j<=i; j++){
			u16 _temp;
			std::cin >> _temp;
			piramida[i].push_back(_temp);
		}
	}
	
	
	u16 min_rok = piramida[0][0];
	for(u16 kolumna=0; kolumna < (n+1)/2; ++kolumna){
		u32 naj_w = najwiekszy_wiersz(kolumna, k);
		naj_w = std::min((u32)n-1, naj_w); // index
		
		if(2*kolumna > naj_w)break;
		
		// minimum w kolumnach
		min_rok = std::min(min_rok, piramida[2*kolumna][kolumna]);
		for(u16 i_rzad=2*kolumna+1; i_rzad <= naj_w; ++i_rzad){
			min_rok = std::min(min_rok, piramida[i_rzad][kolumna]);
			min_rok = std::min(min_rok, piramida[i_rzad][i_rzad-kolumna]);
		}
	}
	
	std::cout<< min_rok <<'\n';
	return 0;
}