Check if can cut horizontally at r1 , at least one apple in matrix ( r , c ) -> r1 , C - 1
if preSum [ r ] - preSum [ r1 ] > 0 : NEW_LINE INDENT dp [ k ] [ r ] += dp [ k - 1 ] [ r1 ] NEW_LINE DEDENT for c1 in range ( c + 1 , C ) : NEW_LINE