DMOPC '15 Contest 1 P5 - Lelei and Dragon Scales

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.5s
Memory limit: 128M

Problem types
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

Lelei is surveying a large field made up of W \times H cells.

A large battle involving dragons has taken place here, and as such there are scales from dragons strewn all about the field. As dragon scales are extremely valuable and fetch a high price, Lelei would like to collect as many as possible. However, a battlefield is a pretty dangerous place to be, so she can only risk spending enough time on it to pick up the scales in a rectangular subsection of the field with a total area up to N.

Given the distribution of scales on the field and the maximum N that Lelei has time for, can you help her determine how many scales she'll end up with if she chooses an optimal section of the field?


Subtask 1 [10%]

1 \le W, H \le 20

Subtask 2 [15%]

1 \le W, H \le 50

Subtask 3 [25%]

1 \le W, H \le 100

Subtask 4 [50%]

1 \le W, H \le 250

Input Specification

The first line of input will contain 3 space-separated integers W, H, and N (N \le W\times H).
The next H lines of input will each contain W space-separated integers in the range [0, 100].

Output Specification

A single integer, the maximum number of scales that Lelei can pick up.

Sample Input 1

5 5 4
0 0 0 0 10
0 5 0 1 2
2 0 3 7 1
8 9 0 1 3
1 5 2 3 7

Sample Output 1



Lelei should explore the 2\times 2 bottom-left corner of the field, which would allow her to collect 8 + 9 + 1 + 5 = 23 scales.

Sample Input 2

1 2 1

Sample Output 2



Lelei only has time for 1 cell, so she should choose the one with 5 scales.


  • 8
    pblpbl  commented on July 9, 2020, 11:30 a.m. edited

    O(N^4) passes, is this intended? edit: it was fixed

    • 5
      maxcruickshanks  commented on July 9, 2020, 3:04 p.m. edit 2

      No, if you look at the editorial, that solution should yield 50% of the points (which it now does).