Canadian Computing Competition: 2019 Stage 1, Senior #5
In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size
consists of
rows, with the
row containing
elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangle. That is, each row is centred around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:
A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing
and the triangle containing
), three sub-triangles of size 3 (one of which contains
). Note that every triangle is a sub-triangle of itself.
You are given a triangle of size
and must find the sum of the maximum elements of every sub-triangle of size
.
Input Specification
The first line contains two space-separated integers
and
(
).
Following this are
lines describing the triangle. The
of these lines contains
space-separated integers
(
), representing the
row of the triangle.
For 4 of the 15 available marks,
.
Output Specification
Output the integer sum of the maximum elements of every sub-triangle of size
.
Sample Input
Copy
4 2
3
1 2
4 2 1
6 1 4 2
Output for Sample Input
Copy
23
Comments