A. Dominos

No Submission Yet

Problem Statement

Everyone knows LHS lunch break sucks. To make up for the disgusting food, Eric decides to play dominoes to distract himself. He put the dominoes into some of the cells of a 2D grid. To test your skills, he wants you to tell him the maximum number of dominoes that will fall if he chooses to knock over at most \(K\) of them (he can only knock them to the left or to the right). For example, if he knocks over a domino to the left, the dominoes to the left of it keep falling until they get to the edge of the grid or to an empty cell. Note that after Eric knocks one domino over, he waits until the dominoes stop falling before knocking over the next one.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb


\(1 \leq N, M, K \leq 100\)

Input format

The first line has three integers \(N\), \(M\), and \(K\) ― the number of rows, the number of columns, and the maximum number of dominoes you can knock over.
The next \(N\) lines have \(M\) integers each, and they describe the grid. If the number in the \(i\)-th row and \(j\)-th column is \(1\), then there is a domino in that cell, and if it is \(0\), then that cell is empty.

Output format

Output the maximum number of dominoes that can fall.

Sample input:

5 5 4
1 1 1 0 1
1 1 0 1 1
1 0 1 1 1
1 1 1 0 0
0 0 1 1 0

Sample output


Sample Explanation

Eric can first knock down \((1,1)\) to the right, causing \(3\) dominoes to fall. Similarly, knocking down \((3,3)\), \((2,4)\) and \((4,1)\) to the right will cause \(3 + 3 + 2 = 8\) dominoes to fall. In total the maximum is \(3 + 8 = 11\)

Contact Us
LIT Discord Server