「题目背景」

小奇不小心让糖果散落到了地上，但是提比已经在来小奇家的路上了，小奇没有足够的时间把糖果都藏起来。

「问题描述」

有n个糖果排成一排，相邻糖果的距离为一个单位长度，编号为1-n，每个糖果的价值为wi，起始时小奇的爪子在第start个糖果，每个单位时间它有两种选择，捡起当前位置的糖果（显然每个糖果只能捡起来一次），把爪子向左或右移动一个单位长度。

它想知道在m个单位时间内能捡起的最大糖果价值和。

「输入格式」

第一行包括3个整数，n，start，m。

第二行n个数，第i个数字表示wi。

「输出格式」

输出一个整数表示答案。

「样例输入」

5 2 7

10 2 20 30 1

「样例输出」

60

「数据范围」

对于 10% 的数据, n ≤ 10;

对于 40% 的数据, n ≤ 500;

另有 20% 的数据, start = 1;

对于 100% 的数据, n ≤ 100000, m ≤ 250000, 0 < wi <= 10^9。

本题来自ioi2014 holiday

题解和代码略。。。