문제
책상 위에 n개의 사탕이 일렬로 놓여 있다.
각 사탕은 '당도'라는 수치가 있어, 왼쪽에서 i번째 사탕의 당도는 a_i이다.
준혁이는 이 n개의 사탕 중 몇 개의 사탕을 먹기로 결심했다.
준혁이는 먹는 사탕들의 당도의 총합을 최대화하고싶다.
그러나, 너무 많은 사탕을 먹는 것은 치아 건강에 좋지 않기에,
준혁이는 연속하여 놓여 있는 두 사탕을 동시에 먹지는 않기로 하였다.
준혁이는 자신이 먹을 사탕의 수를 아직 정하지 못했기 때문에, 각 j(1 <= j <= [n/2])에 대해
자신이 j개의 사탕을 먹을 때의 사탕들의 당도의 합의 최댓값을 구하고자 한다.
당이 떨어져 머리를 굴릴 수 없는 준혁이를 대신해, 여러분이 위의 값을 구해주자.
입력
입력의 첫 줄에는 n이 주어진다. (1 <= n <= 200000)
다음 n개의 줄에는 각 a_i가 주어진다. (1 <= a_i <= 1000000000)
출력
[n/2]줄에 걸쳐, i번째 줄에는 준혁이가 i개의 사탕을 먹을 때의 사탕의 당도의 합의 최댓값을 출력하여라.
예제 #1
5
3
5
1
7
6
7
12
10
예제 #2
20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724
936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029
출처
20201030 집중강화학습2차5번, dennisstar, JOI SC 2017 Day 4 #1
로그인해야 코드를 작성할 수 있어요.