시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 37 | 22 | 19 | 65.517% |
A subarray of an array is a contiguous portion of the array. A partition of an array into subarrays is a collection of subarrays that cover all the array without overlaps (each element in the array belongs to exactly one subarray). For instance, if A = [3, 1, 4, 1, 5] is an array, [3, 1, 4] and [1, 5] form a partition of A into subarrays, while [3, 4, 5] is not a subarray of A.
Those are standard definitions that you may have read elsewhere. So, what’s new here? Well, a few more definitions follow.
Given an array A of integers, a subarray [Ai, Ai+1, . . . , Aj] of A is called a mountain if there exists an index k such that i < k < j, the subarray from Ai to Ak is non-decreasing, and the subarray from Ak to Aj is non-increasing. In simple words, the values in the subarray “go up” until index k and then “go down”, resembling a mountain. Note that a subarray with fewer than three elements cannot be a mountain.
An array of integers is called a beautiful mountain chain if it can be partitioned into mountains, each of them having the same number of elements, except for the last mountain which may have fewer elements.
As an example, [5, 10, 4, 1, 3, 2] is a beautiful mountain chain because it can be partitioned into [5, 10, 4] and [1, 3, 2], being both mountains that have the same number of elements. Another example is the array [5, 10, 4, 4, 10, 20, 30, 20, 2, 3, 1], which is also a beautiful mountain chain because it can be partitioned into [5, 10, 4, 4], [10, 20, 30, 20] and [2, 3, 1].
Given an array of positive integers, where some values can be missing, determine if it is possible to complete the array with positive integers such that it becomes a beautiful mountain chain.
The first line contains an integer N (3 ≤ N ≤ 105) indicating the number of elements in the array. The second line contains N integers A1, A2, . . . , AN (Ai = −1 or 1 ≤ Ai ≤ 109 for i = 1, 2, . . . , N), where Ai = −1 indicates that the i-th element of the array needs to be determined, and a positive value is the actual i-th element of the array.
Output a single line with the uppercase letter “Y
” if it is possible to complete the array with positive integers such that it becomes a beautiful mountain chain, and the uppercase letter “N
” otherwise.
6 5 10 4 1 3 2
Y
11 5 10 4 -1 10 20 30 20 2 3 -1
Y
12 1 3 2 5 -1 8 9 -1 7 -1 4 5
N
ICPC > Regionals > Latin America > Latin America Regional Contests 2020 B번