레이팅 미적용The European Union recently passed a new law stating that all sequences must be
increasing, and starting from January 1, 2026, anyone possessing a sequence that
is not increasing will be strictly penalized. More precisely, a sequence \(a_{1}\), \(a_{2}\), ..., \(a_{n}\)
is illegal if there exists \(i\) (\(1 \le i < n\)) such that \(a_{i} > a_{i+1}\), and otherwise the
sequence is legal.
Ivica recently received a sequence as a gift and is worried that he might get into
trouble because of the new law. Fortunately, Ivica realized that he can take any
two adjacent elements of his sequence and replace them with their sum. More
precisely, if Ivica’s sequence is currently \(a_{1}\), \(a_{2}\), ..., \(a_{m}\), he can choose some \(k\) such
that \(1 \le k < m\) and replace his sequence with \(a_{1}\), \(a_{2}\), ..., a_{\(k - 1\)}, (\(a_{k} + a_{k+1}\)), a_{\(k+2\)}, ..., \(a_{m}\). Ivica can perform
this operation as many times as he wants, and his goal is to obtain a legal sequence using such operations.
Of course, Ivica does not want to completely destroy his sequence, so he would like to obtain the longest
possible legal sequence from his initial sequence. Help Ivica determine the length of the longest legal
sequence he can get from the initial sequence and output any such legal sequence of maximum length.
In the first line, there is a natural number \(n\) (\(1 \le n \le 5000\)), the length of Ivica’s sequence.
In the second line, there are \(n\) natural numbers \(a_{i}\) (\(1 \le a_{i} \le 10^{9}\)), the sequence that Ivica received as a
gift.
In the first line, print a single number m - the length of the longest valid sequence that Ivica can obtain
from the initial sequence.
In the second line, print \(m\) numbers, the elements of one of the valid sequences of length \(m\) that Ivica can
obtain from the initial sequence. If there are multiple such sequences, print any one of them.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(n \le 20\) |
2 | 15점 | \(n \le 100\), \(a_{i} \le 100\) |
3 | 20점 | \(n \le 500\) |
4 | 25점 | \(n \le 1000\) |
5 | 40점 | No additional constraints. 60% of the points for a test case are earned by having a correct output of the 1st line. The remaining 40% of the points for the test case are earned by having a correct output of the 2nd line. |
6
3 2 6 3 3 84
5 6 6 87
3 6 4 2 6 2 55
3 6 6 6 7Clarification of the first example: In the first operation, Ivica will replace the first 2 elements of the
array with their sum and obtain the illegal array [5, 6, 3, 3, 8]. Then, he will replace the third and fourth
elements of the array with their sum and obtain the legal array [5, 6, 6, 8]. It can be shown that this is a
legal array of maximal length that can be obtained from the initial array.