Pie Shop

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Dorian loves pies, and he especially loves his local pie shop - that's why he's bought an all-you-can-eat pie dinner! The pies have been arranged into a grid with R rows and C columns (1 \le R, C \le
16). The pie in row i and column j has a tastiness value t_{i,j} (0 \le t_{i,j} \le 1\,000). Dorian is a messy eater, and whenever he eats a pie, he destroys all pies adjacent to it. He would like to maximize the sum of the tastiness values of the pies he eats, and also figure out how many ways he can achieve this sum.

Two pies respectively located at (r_{1}, c_{1}) and (r_{2}, c_{2}) are adjacent if they are exactly 1 unit of distance apart; that is, |r_{1} - r_{2}| + |c_{1} - c_{2}| = 1.

Input Specification

The first line contains two space-separated integers R and C.
The next R lines each contain C space-separated integers representing the tastiness values of the pies.

Output Specification

A single line containing two space-separated integers: the maximum possible sum and the number of ways to reach this sum. Since the number of ways may be very large, you should give the value modulo 1\,000\,000\,007 (10^{9} + 7).

Sample Input 1

3 4
1 2 3 1
5 7 2 1
1 4 1 0

Sample Output 1

14 3

Sample Input 2

3 3
1 1 0
0 0 1
1 1 0

Sample Output 2

3 5

Scoring

If your output is incorrectly formatted, then your program will score 0 points.
Otherwise, if you correctly determine the first number but not the second, then your program will score 40\% of points for the test case.
If both numbers are correct, then you will receive 100\% of points for the test case.

Subtask Score Constraints
1 30\% R = 1
2 30\% R \le 10
3 40\% No additional restrictions.

Comments

There are no comments at the moment.