Informatica Online Judge

  Bad hair day II [0952 / 03B8]

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


The Champion of this Problem (C++) : gs17044 - ms / 949byte
My Best Submission (C++) : N/A

[JKJeong 2017]
Writer ID : [JKJeong]

Background

경곽이는 Bad hair day를 풀고 나서 다음과 같은 확장된 문제를 생각했다.

기본적으로 Bad hair day와 원리는 같다.단 소들이 한 줄로 서 있는 것이 아니라 피라미드 형태로 서 있고, 바라볼 수 있는 방향이 자신의 위치로부터 왼쪽 아래와 오른쪽 아래 각각 45도 방향의 2곳 중 한 곳으로 선택할 수 있기 때문에 나올 수 있는 경우의 수가 훨씬 많아 졌다.

다음 그림은 Bad hair day II에서의 젖소들의 배치는 다음 그림과 같다.



그리고 아래 그림은 가능한 경로들 중 일부를 보여준다.



[그림 2]의 경로는 10 3 9 4 가 되므로 10에서 3마리 9에서 1마리, 총 4마리를 볼 수 있다.

[그림 3]의 경로는 10 10 7 9 가 되므로 키가 10인 두 번째 소만 2마리를 확인할 수 있으므로 총 2마리를 확인할 수 있다.

[그림 2]에서 확인 가능한 소들의 수를 [그림 2]의 경로의 점수,
[그림 3]에서 확인 가능한 소들의 수를 [그림 3]의 경로의 점수라 정의하자.

자세한 문제는 Bad hair day의 설명을 참고하기 바란다.

피라미드의 층의 수 N과 각 소들의 키가 주어질 때, 모든 경로들의 점수 중 최댓값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 피라미드 층의 수 N이 주어진다.

두 번째 줄부터 N줄에 걸쳐서 i번째줄에 i마리 씩의 소의 키가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= N <= 200
1 <= 각 소들의 키 <= 10

Output

모든 경로들의 점수 중 최댓값을 출력한다.

IO Example

입력
4
10
3 10
9 7 8
10 4 9 10

출력
4

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