最大平均收穫

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type

程設的教學每次上課令你的收穫程度都不一樣

現在總共有n堂社課 你不想斷斷續續地來

但你想要最大化你的平均收穫程度

因此你選擇開始課程的堂數i 跟結束課程的堂數j

而在第i堂課到第j堂課你每堂都要到(就算收穫是負的)

請問 在讓你自由選擇i j的情況下 你的最大平均收穫到多少呢?

最大平均收穫=你來的連續課程收穫度/你來的堂數


Input

第一行為兩正整數n,k 代表總共有n堂社課 再來一行有以空白分隔的n個到小數點後k位的浮點數,依序表示第1堂到第n堂社課你的收穫程度

Output

輸出你的最大平均收穫

Constraints

1 <= n <= 1000000

-1000 <= arr[i] <= 1000

0 <= k <= 100

(5%) n <= 2 , k = 0

(5%) n <= 2 , k <= 5

(10%) n <= 100 , k = 0

(30%) n <= 100 , k <= 5

(30%) n <= 10000 , k <= 5

(20%) n <= 1000000 , k <= 5

(10%) n <= 1000000 , k <= 100

Sample Input
5 0

-2 -1 5 -4 -3
Sample Output
5

Comments

There are no comments at the moment.