No.324 The Cycle Graph Lying on the Road
タグ : / 解いたユーザー数 89
作問者 :
tubo28
Note
This problem was created as the problem for day 17 of Advent Calendar Contest Advent Calendar 2015.
Problem Statement
One day, while walking along the road, yuki found an impressive-looking cycle graph lying on the ground.
The graph consists of $n$ edges and vertices, and the edges are numbered from $1$ to $n$ in clockwise order.
The value of edge $i$ is $w_i$.
Intrigued, yuki decided to pocket this graph.
Since yuki's bag holds exactly $m$ vertices, yuki decided to take home an induced subgraph with $m$ vertices.
That is, if both endpoints of an edge are taken home, that edge must also be taken home.
The value of a subgraph is the sum of the values of the edges it contains.
Find the maximum value of a graph that can be taken home.
Input
$n$ $m$
$w_{1} \ w_{2} \ w_{3} \ \cdots \ w_{n}$
The input satisfies the following constraints.
- All values are integers
- $3 \leq n \leq 3000$
- $0 \leq m \leq n$
- $-300 \leq w_{i} \leq 300$
Output
Output the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
6 3 1 2 3 4 5 6
Output
11
Sample 2
Input
6 3 1 -2 -3 4 -5 6
Output
7
Sample 3
Input
6 3 -1 -2 -3 -4 -5 -6
Output
0
Sample 4
Input
6 4 -1 -2 -3 -4 -5 -6
Output
-3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。