Informatica Online Judge

  영역 구분 2 [2347 / 092B]

Time Limit(Test case) : 100 (ms)
Number of users who solved : 18   Total Tried : 26


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

[JKJeong 2019]

Background

영역 구분 문제에서는 2^n길이의 정사각형을 재귀적으로 4등분한다.

영역구분 문제를 참고하려면 [클릭]

영역 구분과는 달리 각 영역의 값은 0이상 20이하의 자연수이다.

이번 문제에서는 한 변의 길이가 2^k (0 <= k <= n) 인 각 영역에 대해서 해당 영역의 합을 구하고 각 k에 대한 합의 최댓값을 구하면 된다.

예를 들어 n = 2이고 주어진 값이 다음과 같을 때

1 2 5 6
4 3 16 10
11 12 13 14
7 8 9 15

한 변의 길이가 2^2일 때는 전체 영역의 합이므로 136이다.
한 변의 길이가 2^1일 때 나눠진 사각형은 각각

1 2
4 3

5 6
16 10

11 12
7 8

13 14
9 15

이며 합이 가장 큰 사각형은 마지막 사각형이고 합은 51이다.

마지막으로 한 변의 길이가 2^0일 때는 각 원소가 각 사각형이므로 가장 합이 큰 값은 16이다.

이와 같이 각 길이별 영역의 최대합을 각각 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 변의 길이 2^n을 나타내는 n이 입력된다.

두 번째 줄부터 n줄에 걸쳐서 각 n개씩 0~19범위의 값들이 공백으로 구분되어 입력된다.

[입력값의 정의역]

1 <= n <= 10

Output

n+1줄에 걸쳐서 각 2^n ... 2^0까지 변의 길이를 가지는 영역의 합의 최댓값들을 한 줄에 하나씩 출력한다.

IO Example

입력
2
1 2 5 6
4 3 16 10
11 12 13 14
7 8 9 15

출력
136
51
16

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