CCC '19 S5 - Triangle: The Data Structure

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 M consists of M rows, with the i^{th} row containing i 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 (3,1,2) and the triangle containing (4,6,1)), three sub-triangles of size 3 (one of which contains (2,2,1,1,4,2)). Note that every triangle is a sub-triangle of itself.

You are given a triangle of size N and must find the sum of the maximum elements of every sub-triangle of size K.

Input Specification

The first line contains two space-separated integers N and K (1 \le K \le N \le 3\,000).

Following this are N lines describing the triangle. The i^{th} of these lines contains i space-separated integers a_{i,j} (0 \le a_{i,j} \le 10^9), representing the i^{th} row of the triangle.

For 4 of the 15 available marks, N \le 1000.

Output Specification

Output the integer sum of the maximum elements of every sub-triangle of size K.

Sample Input

4 2
3
1 2
4 2 1
6 1 4 2

Output for Sample Input

23

Comments


  • 0
    noYou  commented on Aug. 15, 2020, 12:17 p.m.

    Can java have a language specific limit, since bufferedReader takes 0.5s (half the given runtime) to take input in the worst case?


  • 4
    ASmartWalrus  commented on Jan. 14, 2020, 9:36 p.m.

    I can't seem to have my code get full points, I keep getting TLE on Batch 3 Case 3. This is despite having the CCCgrader pass my code? Can anyone help?


    • 5
      c  commented on Jan. 14, 2020, 10:01 p.m.

      CCC Grader is too fast and the data seems to be not strong enough to break this solution.


    • 6
      Plasmatic  commented on Jan. 14, 2020, 10:00 p.m. edited

      Your solution is O(N^3) which cannot pass when N=3000

      CCCGrader is just stupid fast


      • 2
        Dingledooper  commented on March 12, 2020, 2:15 a.m.

        I just tried submitting an O(N^2K) DP solution, and it passes.


        • 2
          sushi  commented on March 12, 2020, 9:13 a.m.

          This is due to the new judges. It looks like we need to adjust the time limit.


  • 6
    AryanG  commented on Sept. 26, 2019, 7:33 p.m.

    Is there a specific reason as to why I might get an IR in python 3. It doesn't actually tell me what went wrong although the status codes indicate it should.


    • 8
      N3RDSLQYER84  commented on Sept. 27, 2019, 5:42 p.m.

      You recur too many times(RecursionError).


      • 6
        AryanG  commented on Sept. 28, 2019, 10:01 a.m.

        Thanks


  • 14
    Darcy_Liu  commented on March 21, 2019, 6:20 p.m.

    triangule should be triangle


    • 10
      Kirito  commented on March 21, 2019, 6:21 p.m. edited

      Fixed, thanks for pointing that out!