← 返回题目列表

AtCoder · arc092_c

E. 双方合并

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

你有一个长度为的整数序列 N: a_1, a_2, ..., a_N.

重复执行以下操作,直到序列的长度变为 1:

  • 首先,选择序列的一个元素。
  • 如果该元素位于序列的任一端,则删除该元素。
  • 如果该元素不在序列的任一端,则将该元素替换为与其相邻的两个元素的总和。然后,删除这两个元素。

您希望最大化序列中保留的最终元素。

找到最终元素的最大可能值,以及实现它的方法。

约束

  • 所有输入值均为整数。
  • 2 \leq N \leq 1000
  • |a_i| \leq 10^9

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 ... a_N

输出

  • 在第一行中,打印序列中最后一个元素的最大可能值。
  • 在第二行中,打印您执行的操作数。
  • 在 (2+i)-第行,如果在 i- 第一个操作是 x此时序列中从左边算起的第一个元素,打印 x.
  • 如果有多种方法可以实现最终元素的最大值,则可以打印其中任何一种。

示例输入 1

5
1 4 3 7 5

示例输出 1

11
3
1
4
2

顺序将更改如下:

  • 第一次操作后: 4, 3, 7, 5
  • 第二次操作后: 4, 3, 7
  • 第三次操作后: 11(4+7)

示例输入 2

4
100 100 -1 100

示例输出 2

200
2
3
1
  • 第一次操作后: 100, 200(100+100)
  • 第二次操作后: 200

示例输入 3

6
-1 -2 -3 1 2 3

示例输出 3

4
3
2
1
2
  • 第一次操作后: -4, 1, 2, 3
  • 第二次操作后: 1, 2, 3
  • 第三次操作后: 4

示例输入 4

9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 4

5000000000
4
2
2
2
2