Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Problem C: Pie Shop

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 ≤ R, C ≤ 16). The pie in row i and column j has a tastiness value t_i,j (0 ≤ t_i,j ≤ 1000). 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₁, c₁) and (r₂, c₂) are adjacent if they are exactly 1 unit of distance apart; that is, |r₁ − r₂| + |c₁ − c₂| = 1.

Input Format

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 Format

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 1000000007 (10⁹ + 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 1 [30% of points]

R = 1.

Subtask 2 [30% of points]

R ≤ 10.

Subtask 3 [40% of points]

There are no additional restrictions.

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 15, 2014
Author: nullptr

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)