시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 33 | 15 | 12 | 42.857% |
For a sequence $a_{1...n}$, define $f(a)$ as $$f(a) = \max\limits_{1 \le l \le r \le n} \sum\limits_{i = l}^{r} a_i\text{.}$$
Given a sequence $b_{1...n}$, you need to permute $b_{1...n}$ to get $b'_{1...n}$ and minimize $f(b')$.
The first line contains a single integer $n$ ($1 \le n \le 16$).
The second line contains $n$ integers $a_{1...n}$ ($|a_i| \le 10^5$).
Output the minimum possible $f(b')$.
4 1 -1 1 1
2
6 4 -4 5 -20 6 7
9