| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 2048 MB | 70 | 29 | 17 | 32.075% |
Given an array $A$ of length $N,ドル a subarray $A[l \ldots r]$ is defined as the part of the array $A$ that includes only the elements located at positions from $l$ to $r$ inclusively. The cost of a subarray is defined as the product of the length of the subarray and the sum of its two smallest elements.
For example, let the array be $A = [5, 1, 3, 5, 3]$. Let us consider the subarray $A[2 \ldots 4] = [1, 3, 5]$. Its length is 3ドル,ドル its smallest element is 1ドル,ドル and its second smallest element is 3ドル$. Therefore, its cost is 3ドル \cdot (1 + 3) = 12$. Let us consider another subarray, $A[1 \ldots 2] = [5, 1]$. Its length is 2ドル,ドル its smallest element is 1ドル,ドル and its second smallest element is 5ドル$. Therefore, its cost is 2ドル \cdot (1 + 5) = 12$.
Note that if the minimal value occurs more than once in a subarray, it is counted several times. For example, the length of the subarray $A[3 \ldots 5] = [3, 5, 3]$ is 3ドル,ドル its smallest element is 3ドル,ドル and its second smallest element is also 3ドル$. Therefore, its cost is 3ドル \cdot (3 + 3) = 18$.
Given an array, find the maximum cost over all subarrays of at least two elements. That is, you need to find the maximum cost over all subarrays $A[l \ldots r],ドル where 1ドル \le l < r \le N$.
The first line contains $N$ (2ドル \le N \le 10^6$), the length of the array. The second line contains $N$ integers $A_1, A_2, \dots, A_N$ (1ドル \le A_i \le 10^9$).
Output a single integer, the maximum cost over all subarrays of at least two elements.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $N \le 800$. |
| 2 | 7 | $N \le 5,000円$. |
| 3 | 10 | $N \le 20,000円$. |
| 4 | 24 | $N \le 10^5$ and $A_i$ are selected uniformly randomly from 1ドル \ldots 10^9$. |
| 5 | 17 | 2ドル \le A_i \le \sqrt{N}$ for all 1ドル \le i \le N$. |
| 6 | 36 | No additional constraints. |
5 5 1 3 5 3
20
The maximum cost is achieved for the subarray $A[1 \ldots 5]$: its length is 5ドル,ドル the two smallest elements are 1ドル$ and 3ドル,ドル and the cost is 5ドル \cdot (1 + 3) = 20$.
7 1 1 3 5 10 77 5
174
The maximum cost is achieved for the subarray $A[5 \ldots 6]$: its length is 2ドル,ドル its two smallest elements are 10ドル$ and 77ドル,ドル and the cost is 2ドル \cdot (10 + 77) = 174$.
3 1 2 3
10
The maximum cost is achieved for the subarray $A[2 \ldots 3]$: its length is 2ドル,ドル its two smallest elements are 2ドル$ and 3ドル,ドル and the cost is 2ドル \cdot (2 + 3) = 10$.