P6648 [CCC 2019] Triangle: The Data Structure

In Shuchong’s parallel universe, the most important data structure in computer science is the triangle. Note: Since the original dataset package was too large, this problem removed some testdata. The removed test points are: - Subtask 1: 1 ~ 10 - Subtask 2: 1 ~ 10 So the test points included in this problem are: - Subtask 1: 11 ~ 26 - Subtask 2: 11 ~ 24 If you want to test the missing test points, please go to [here](https://www.luogu.com.cn/problem/U120704).

A triangle of size $m$ consists of $m$ rows, and row $i$ contains $i$ elements. Also, these rows must be arranged in the shape of an equilateral triangle. For example, the following is a triangle with $m = 4$.  Each triangle also contains sub-triangles. For example, the triangle above contains: - $10$ triangles of size $1$. - $6$ triangles of size $2$. - $3$ triangles of size $3$. Note that each triangle is also a sub-triangle of itself. Now you are given a triangle of size $n$. For every sub-triangle of size $k$, find the sum of the maximum value among the numbers inside that sub-triangle.

The first line contains two integers $n, k$, representing the size of the triangle and the required size of the sub-triangles. The next $n$ lines describe the triangle: line $i$ contains $i$ integers.

Output one integer: the sum, over all sub-triangles of size $k$, of the maximum value inside each sub-triangle.

#### Constraints - Subtask 1 (25 pts): $n \le 1000$. - Subtask 2 (75 pts): no special constraints. For $100\%$ of the data, $1 \le k \le n \le 3000$, and $0 \le$ each number in the triangle $\le 10^9$. #### Notes **Translated from [CCC 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) Senior T5 [Triangle: The Data Structure](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%201/seniorEF.pdf).** Translator: @[一只书虫仔](https://www.luogu.com.cn/user/114914). Translated by ChatGPT 5