718 . 最大平均區間

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

hehe

User's AC Ratio

78.3% (18/23)

Submission's AC Ratio

28.4% (21/74)

Tags

apcsc apcsc-greedy

Description

學姐最近開始打工，第 i 天她賺了 Ai 塊錢。她決定跟朋友炫耀她平均一天能賺多少錢，所以她打算找 L 和 R 使得在第 L 天到第 R 天之間每天平均賺的錢最多，但是如果這個期間只有一天的話會被他的朋友抓包，換句話說，學姐想要找 L,R 使得 [AL,AL+1,⋯,AR] 的平均最大且 L≠R 。請幫學姐找到最好的平均日薪吧！

Input Format

輸入有兩行，第一行包含一個正整數 N，代表學姐打工了 N 天，第二行有 N 個正整數，第 i 個正整數是 Ai，代表第 i 天打工的薪資。

  • 2≤N≤3⋅105
  • 0≤Ai≤108

Output Format

輸出只有一行，包含兩個正整數 P 和 Q，代表最大的平均日薪為 PQ，這必須是一個最簡分數，也就是說 P,Q 互質。

Sample Input 1

5
1 3 4 2 3

Sample Output 1

7 2

Sample Input 2

3
0 0 0

Sample Output 2

0 1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~33 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
22 3000 524288 65536 2
23 3000 524288 65536 2
24 3000 524288 65536 2
25 3000 524288 65536 2
26 3000 524288 65536 2
27 3000 524288 65536 2
28 3000 524288 65536 2
29 3000 524288 65536 2
30 3000 524288 65536 2
31 3000 524288 65536 2
32 3000 524288 65536 2
33 3000 524288 65536 2
Submit
Back to Top