codeforces467C

George and Job

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p₁, p₂, ..., p_n. You are to choose k pairs of integers:

[l₁, r₁], [l₂, r₂], ..., [l_k, r_k] (1 ≤ l₁ ≤ r₁ < l₂ ≤ r₂ < ... < l_k ≤ r_k ≤ n; r_i - l_i + 1 = m),

in such a way that the value of sum is maximal possible. Help George to cope with the task.

Input

The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p₁, p₂, ..., p_n (0 ≤ p_i ≤ 10⁹).

Output

Print an integer in a single line — the maximum possible value of sum.

Examples

Input

5 2 1
1 2 3 4 5

Output

Input

7 1 3
2 10 7 18 5 33 0

Output

61

sol：题意比较gou，用 K 条长度为 m 的不相交线段覆盖一段长度为 n 的数列，使得覆盖到的和最大
XJBdp应该不难，n²dp即可完美AC此题

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

int n,m,K;

ll Cost[N],Qzh[N];

ll dp[N][N];

int main()

{

    int i,j;

    R(n); R(m); R(K);

    for(i=;i<=n;i++) R(Cost[i]);

    for(i=;i<=n;i++) Qzh[i]=Qzh[i-]+Cost[i];

    dp[][]=;

    for(j=;j<=K;j++)

    {

        for(i=j*m;i<=n;i++)

        {

            dp[i][j]=max(dp[i-][j],dp[i-m][j-]+Qzh[i]-Qzh[i-m]);

        }

    }

    Wl(dp[n][K]);

    return ;

}

/*

Input

5 2 1

1 2 3 4 5

Output

9

Input

7 1 3

2 10 7 18 5 33 0

Output

61

*/

巴特西

codeforces467C

George and Job

最新文章

热门文章