c364: 我鄙視你
Tags :
Accepted rate : 32人/94人 ( 34% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-04-17 14:05

Content

今天升旗的方式比較特別,每個班排成一直列就好。

班上的高個子這時便開始鄙視矮子,只要相鄰的甲同學比乙同學高,則甲同學會鄙視乙同學。若乙同學另一邊的丙同學也比甲同學矮,則甲同學也會鄙視丙同學,會連續鄙視到一個身高不矮於甲同學的人。同時,甲同學也可以往另一邊鄙視其他同學。

假設班上有 $\color{black}{N}$ 個人,每個人的身高分別為 $\color{black}{h_1, h_2, ..., h_N}$,請求出每個同學鄙視的人的身高總和。

Input

輸入的第一行有兩個正整數 $\color{black}{N\ (1 \le N \le 10^6)}$,表示有 $\color{black}{N}$ 個同學。

第二行接下來會有 $\color{black}{N}$ 個正整數 $\color{black}{h_1, h_2, ..., h_N\ (1 \le h_i \le 10^9)}$ 表示每個同學的身高。

Output

每一行輸出第 $1$ 個、第 $2$ 個、…、第 $\color{black}{N}$ 個同學鄙視的人的身高總和。

Sample Input #1
5
140 150 170 180 160
Sample Output #1
0
140
290
620
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (6%): 1.0s , <1M
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 1.0s , <1M
公開 測資點#5 (6%): 1.0s , <1M
公開 測資點#6 (6%): 1.0s , <1M
公開 測資點#7 (6%): 1.0s , <1M
公開 測資點#8 (6%): 1.0s , <1M
公開 測資點#9 (6%): 1.0s , <10M
公開 測資點#10 (6%): 1.0s , <10M
公開 測資點#11 (6%): 1.0s , <10M
公開 測資點#12 (6%): 1.0s , <10M
公開 測資點#13 (6%): 1.0s , <10M
公開 測資點#14 (6%): 1.0s , <10M
公開 測資點#15 (6%): 1.0s , <10M
公開 測資點#16 (6%): 1.0s , <10M
Hint :
  • 對於第 0 ~ 6 筆測資,$\color{black}{N \le 3000}$。
  • 對於第 7 ~ 16 筆測資,無額外限制。
Tags:
出處:
106 學年度第一次 CRC 附電盃程式設計團體賽 [管理者:
hsnucrc (師大附中電算社)
]


ID User Problem Subject Hit Post Date
24375
fire5386 (皮卡丘)
c364
想法
364 2021-02-10 11:10