Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.


By borisal · Limits 1s, 256 MB

Dhoni has a field divided into n×mn\times m squares of the same area. The amount of rice at each square will be given. He wants to divide his field into three parts containing AABB, and CC tons of rice. The field should be divided by two parallel lines. The lines should be parallel to one side of the field. The lines should not intersect any square. Each resulting part of the field should consist of at least one square.

Your task is to find the number of ways to divide the field as is described above, that is, to mark two lines, dividing the field into three parts so that one of the resulting parts contain AA tons of rice, BB on another one, and CC on the remaining one.


The first line contains space-separated integers nn and mm — the sizes of the original field (1n,m1000,max(n,m)3)(1 \le n, m \le 1000, \max(n, m) \ge 3). Then the field's description follows:
nn lines, each containing mm space-separated integers Rij(0Rij100)R_{ij} (0 \le R_{ij} \le 100) — the number of tons of rice each square contains.

The last line contains three space-separated integers A,B,C (0A,B,C1000000)A, B, C (0 \le A, B, C \le 1000000).


Print the answer to the problem: the number of ways to divide Dhoni’s field.


3 3
0 0 0
0 0 1
1 1 0
2 1 0
3 3
1 2 3
3 1 2
2 3 1
5 6 7
2 5
1 1 1 1 1
2 2 2 2 2
3 6 6
3 3
1 1 1
1 1 1
1 1 1
3 3 3



78% Solution Ratio

naeem4265Earliest, 1M ago

HSTU_TREENITYFastest, 0.0s

S_SubrataLightest, 131 kB

fahimcp495Shortest, 1257B


Login to submit


We can divide this field row-wise or column-wise. If we fix the two parts, the other part is obvious...

Toph uses cookies. By continuing you agree to our Cookie Policy.