Informatica Online Judge

  사각형의 넓이 [2346 / 092A]

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


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

[JKJeong 2019]

Background

한 변의 길이가 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

2 5
3 16

5 6
16 10

4 3
11 12

3 16
12 13

16 10
13 14

11 12
7 8

12 13
8 9

13 14
9 15

이며 합이 가장 큰 사각형은

16 10
13 14

이고 합은 53이다.

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

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

Input

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

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

[입력값의 정의역]

1 <= n <= 10

Output

2^(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
53
16

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