A - Abundant Resources
Editorial
/


Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
東西に細長い土地があります。 この土地は、N 個の区画が東西に並んだ形をしており、西から i 番目の区画は区画 i と呼ばれます。
それぞれの区画には地下資源があることがわかっており、区画 i の資源埋蔵量は A_i です。
1 以上 N 以下のそれぞれの整数 k について、次の問題の答えを求めてください。
- 連続する k 個の区画を選んだとき、それらの区画の資源埋蔵量の総和として考えられる最大値はいくらか。
制約
- 1 \leq N \leq 3000
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \cdots A_N
出力
N 行出力せよ。 k 行目には、連続する k 個の区画の資源埋蔵量の総和の最大値を出力せよ。
入力例 1
4 4 1 3 3
出力例 1
4 6 8 11
k=1 のとき、区画 1 を選ぶと資源埋蔵量の総和は 4 となり、これが最大です。
k=2 のとき、区画 3,4 を選ぶと資源埋蔵量の総和は 3+3=6 となり、これが最大です。
k=3 のとき、区画 1,2,3 を選ぶと資源埋蔵量の総和は 4+1+3=8 となり、これが最大です。
k=4 のとき、区画 1,2,3,4 を選ぶと資源埋蔵量の総和は 4+1+3+3=11 となり、これが最大です。
入力例 2
5 10 20 30 40 50
出力例 2
50 90 120 140 150
入力例 3
10 61049214 115057849 356385814 932678664 505961980 877482753 476308661 571830644 210047210 873430114
出力例 3
932678664 1438640644 2316123397 2792432058 3364262702 3720648516 4447740026 4804125840 4919183689 4980232903