20498번 - C = 15

위 메일은 실제로 욱제가 교수님께 보냈던 메일이며, 미적분을 컴퓨터수학으로 잘못 적어서 정정 메일을 보냈고, 정정 메일에는 수업 시간을 잘못 적어서 보냈다는 비하인드가 있다.

욱제는 중간고사에서 11점을 받았다. 기말고사에서 4점 이상을 받아 도합 15점을 넘지 못하면 F, 넘으면 C를 받게 된다. (만점은 160점이다.) (실화를 기반으로 한 이야기이다.)

욱제가 공부해야 할 문제 유형은 총 $2^{k}-1$개가 있다. 각 유형 사이의 관계는 노드에 가중치가 있는 포화이진트리로 표현된다. 각 노드는 유형, 노드의 가중치는 유형의 중요도를 의미한다. 루트 노드의 번호는 $1$이며, $N$번 노드의 좌우 자식 노드는 각 $N \times 2$, $N \times 2+1$이다.

욱제는 단 한 번, 정확히 $k$개의 연속된 리프 노드에 ★족보의 힘★을 사용할 수 있다. $[L, R]$ 구간의 리프 노드에 ★족보의 힘★을 사용하면, $LCA(L, R)$에서 출발해 $L, L+1, ..., R-1, R$ 각각으로 도착하는 단순 경로들에 포함된 모든 노드를 하나의 노드로 합쳐버릴 수 있다! 합쳐진 노드의 가중치는 기존 노드들의 가중치 합이다. 기존 노드들에 연결되어 있던 간선들은 모두 합쳐진 노드로 연결된다.

욱제에게 남은 시간은 제한적이다. 욱제는 임의로 두 노드를 골라, 두 노드 사이의 단순 경로 내에 있는 모든 과목을 공부할 것이다. 욱제는 공부한 과목들의 중요도 합이 최대가 되도록 하고 싶다. ★족보의 힘★은 필요에 따라 사용하지 않을 수도 있다.

당신은 욱제의 학부모이다. 철부지 아들을 위해 ★족보의 힘★을 적절히 사용하고, 단순 경로를 잘 골라서 공부한 과목들의 중요도 합을 최대로 만들어 주자.

첫째 줄에 유형의 개수 $N$이 주어진다.

둘째 줄에 $N$개 유형의 중요도 $W_{i}$이 1번 유형부터 순서대로 주어진다.

중요도의 최대 합을 출력한다.

• $1 \le N \le 262\,143 = 2^{18} - 1$
• 양의 정수 $k$에 대해, $N = 2^{k}-1$이 항상 성립한다.
• $1 \le W_{i} \le 100\,000\,000$

욱제는 결국 시험 공부를 하나도 안 하고 4점을 넘어서 C+을 받았다.