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
#include <cstdint>
#include <cstring>
#include <iostream>

using u32 = std::uint32_t;

namespace {

constexpr std::size_t size = 2020;

// access cost depending on vintage
u32 costs[size];

u32 get_triangle_elem_count(u32 n) {
    return ((n+1)*n)/2;
}

u32 calculate_access_cost(u32 n, u32 k) {
    if (k == 1) {
        return n;
    }

    if (k == n) {
        return n;
    }

    u32 big_triangle = get_triangle_elem_count(n);
    u32 left_triangle = get_triangle_elem_count(k-1);
    u32 right_triangle = get_triangle_elem_count(n-k);

    return big_triangle - left_triangle - right_triangle;
}

} // namespace

int main(void) {
    std::memset(costs, 0xff, size*sizeof(u32));

    u32 height;
    u32 bootle_count;

    std::cin >> height >> bootle_count;

    for (u32 n = 1; n <= height; ++n) {
        for(u32 k = 1; k <= n; ++k) {
            u32 vintage;
            std::cin >> vintage;
            u32 cost = calculate_access_cost(n, k);
            if(cost < costs[vintage]) {
                costs[vintage] = cost;
            }
        }
    }

    for (u32 n = 1; n <= size; ++n) {
        if(bootle_count >= costs[n]) {
            std::cout << n;
            break;
        }
    }

    return 0;
}