# CF467C George and Job

• 142通过
• 393提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 优先队列 前缀和 动态规划,动规,dp
• 难度 提高+/省选-
• 时空限制 1000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

# 题目描述

新款手机 iTone6 近期上市，George 很想买一只。不幸地，George 没有足够的钱，所以 George 打算当一名程序猿去打工。现在George遇到了一个问题。 给出一组有 $n$ 个整数的数列 $p_1,p_2,...,p_n$ ,你需要挑出 $k$ 组长度为 $m$ 的数，要求这些数互不重叠 即$[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<l_{k}<=r_{k}<=n; r_{i}-l_{i}+1=m)$ 使选出的数的和值最大，请你帮助George码出这份代码

# 输入输出格式

## 输入格式

第1行读入3个整数 $n , m , k(1\leq(m×k)\leq n\leq5000) (1\leq(m×k)\leq n\leq5000)$, 第2行读入 $n$ 个数 $p_1,p_2,...,p_n$

## 输出格式

输出1个整数，代表可以取到的最大值

# 输入输出样例

如原版 translated by @Venus

## 题目描述

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_{1},p_{2},...,p_{n}$ . You are to choose $k$ pairs of integers:

$[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<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.

## 输入输出格式

输入格式：

The first line contains three integers $n$ , $m$ and $k$ $(1<=(m×k)<=n<=5000)$ . The second line contains $n$ integers $p_{1},p_{2},...,p_{n}$ $(0<=p_{i}<=10^{9})$ .

输出格式：

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

## 输入输出样例

输入样例#1： 复制
5 2 1
1 2 3 4 5

输出样例#1： 复制
9

输入样例#2： 复制
7 1 3
2 10 7 18 5 33 0

输出样例#2： 复制
61

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。