Croatian Olympiad in Informatics
April \(25^{th}\) 2021
In an alternate reality Earth 616 young Stjepan lives a totally different life. Currently he is enrolled in a
bri\(ck-cr\)afting course at School of Arts and Design. As every child there, he is obsessed with patterns. For
example, his homework requires him to build a brick wall using \(N\) bricks. But he will not start building
until he is satisfied with his t\(wo-di\)mensional sketch.
On the sketch, every brick can be represented as a rectangle with unit size height and width of size \(d\)\(i\). He
chooses the order of bricks beforehand and starts sketching from the bott\(om-mo\)st row.
In the first row he will place some number of bricks going from left to right. In the second row he will be
placing bricks from right to left and the first brick in the second row will align with the last brick in the
first row (their right edges will align). Next, in the third row he will be placing the bricks again from left
to right. The first brick in the third row will align with the last from the second row but this time the left
edges. He continues this process until there are no bricks left. He may choose to build wall with arbitrary
number of rows.
Stjepan uses super cement so a brick may be placed in the wall so that there is no other brick directly
underneath. Beauty of the wall is a number of places where 4 bricks touch
For a given order of bricks and their respective sizes help find the largest possible beauty of the wall.

Subtask 1 (9 points): \(1 \le N \le 20\)

Subtask 2 (11 points): \(1 \le N \le 80\)

Subtask 3 (13 points): \(1 \le N \le 500\), \(1 \le M \le 2\)

Subtask 4 (15 points): \(1 \le N \le 500\)

Subtask 5 (52 points): \(1 \le N \le 5\,000 2\) od 7 Croatian Olympiad in Informatics April \(25^{th}\) 2021

First line contains an integer \(N\) from the task description.
Second line contains \(N\) integers \(d_{i}\) from the task description.

Print the largest possible beauty of any wall that can be built.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Olympiad