#P5892. [IOI2014] holiday 假期

[IOI2014] holiday 假期

题目描述

健佳正在制定下个假期去台湾的游玩计划。在这个假期,健佳将会在城市之间奔波,并且参观这些城市的景点。

在台湾共有 nn 个城市,它们全部位于一条高速公路上。这些城市连续地编号为 00n1n-1

对于城市 ii0<i<n10 < i < n-1 )而言,与其相邻的城市是 i1i-1i+1i+1。但是对于城市 00,唯一与其相邻的是城市 11。而对于城市 n1n-1,唯一与其相邻的是城市 n2n-2

每个城市都有若干景点。健佳有 dd 天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天,健佳可以选择去一个相邻的城市,或者参观所在城市的所有景点,但是不能同时进行。即使健佳在同一个城市停留多次,他也不会去重复参观该城市的景点。请帮助健佳策划这个假期,以便能让他参观尽可能多的景点。

输入格式

  • 11 行:有三个非负整数, nn 代表城市数目,startstart 代表起点城市编号,dd 代表假期天数。
  • 22 行:nn 个非负整数 a[0],,a[n1]a[0],\cdots, a[n-1],对于 0in10 \le i \le n-1a[i]a[i] 代表城市 ii 的景点数目。

输出格式

  • 共一行,最多参观的景点数目。
5 2 7
10 2 20 30 1

60

提示

子任务

在所有的子任务中,有 0d2n+floor(n/2)0 \le d \le 2n+floor(n/2)。 而且,每个城市中的景点数都是非负整数。

子任务 分值 nn 各城市景点数的最大值 起点城市
11 77 2n202 \le n \le 20 10910^9 无限制
22 2323 2n1052 \le n \le 10^5 100100 城市 00
33 1717 2n3×1032 \le n \le 3 \times 10 ^3 10910^9 无限制
44 5353 2n1052 \le n \le 10^5