Informatica Online Judge

  Arbeit #2 [2263 / 08D7]

Time Limit(Test case) : 500(ms)
Number of users who solved : 0   Total Tried : 0


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[35th 김민성]

Background

평소 주변에서 소금이라고 불릴 정도로 소금에 관심이 많은 학생인 선우는 이번 방학에도 염전에서 아르바이트를 해서 희귀한 한정판 소금을 수집하기로 결심했다.

선우가 맡은 염전은 한 변이 n인 직사각형으로 이루어져 있으며, 선우는 반드시 하루에 1X1 또는 1X2 또는 1X3 크기의 영역을 처리해야 한다.

염전에서 채취할 수 있는 소금은 두 번째 날부터 하루에 1씩 감소하기 때문에, 선우는 최대한 많은 소금을 채취할 수 있는 방법으로 염전을 처리하려고 한다.

선우는 문득 자신이 받아 갈 수 있는 급여가 얼마나 될 지 궁금해졌다.

선우를 도와서 주어진 염전에서 채취할 수 있는 소금의 양의 최댓값을 구하고, 그만큼의 양을 채취할 수 있는 방법의 가짓수를 구하도록 하자.

단, 염전의 모든 영역을 반드시 처리해야 하며, 영역이 한 칸이 남았다고 해서 염전 바깥을 밀 수는 없다.

또한 가짓수가 너무 많을 수 있으므로 251353835로 나눈 나머지를 구한다.

Input

첫 줄에 염전의 크기에 해당되는 n ( 3 <= n <= 11 ) 이 주어진다.
이후 n줄에 걸쳐서 각 영역의 소금의 양에 해당되는 n개의 정수 데이터 k ( 1000 <= k <= 10000 ) 가 주어진다.


Subtask 1 : n = 3
Subtask 2 : 3 <= n <= 10
Subtask 3 : 3 <= n <= 11

Output

첫 줄에 채취할 수 있는 소금의 양의 최댓값을 출력한다.
두번째 줄에 채취할 수 있는 방법의 가짓수를 251353835로 나눈 나머지를 출력한다.

IO Example

Input
4
1020 1040 1060 1080
2010 2030 2050 2070
3015 3035 3055 3075
4005 4025 4045 4065

Output
40645
16

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]