DMOPC '15 Contest 1 P5 - Lelei and Dragon Scales

View as PDF

Submit solution


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

Author:
Problem types

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?

Constraints

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

23

Explanation for 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
0
5

Sample Output 2

5

Explanation for Sample Output 2

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


Comments

There are no comments at the moment.