M. April Fools' Problem (easy)

Codeforces

IDCF802M

Time2000ms

Memory256MB

Difficulty—

greedysortings

English · Original

Chinese · Translation

Formal · Original

The marmots have prepared a very easy problem for this year's HC2 – this one. It involves numbers _n_, _k_ and a sequence of _n_ positive integers _a_1, _a_2, ..., _a__n_. They also came up with a beautiful and riveting story for the problem statement. It explains what the input means, what the program should output, and it also reads like a good criminal. However I, Heidi, will have none of that. As my joke for today, I am removing the story from the statement and replacing it with these two unhelpful paragraphs. Now solve the problem, fools! ## Input The first line of the input contains two space-separated integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 2200). The second line contains _n_ space-separated integers _a_1, ..., _a__n_ (1 ≤ _a__i_ ≤ 104). ## Output Output one number. [samples]

土拨鼠为今年的 HC#cf_span[2] 准备了一个非常简单的题目——就是这个。它涉及数字 #cf_span[n]、#cf_span[k] 和一个由 #cf_span[n] 个正整数组成的序列 #cf_span[a1, a2, ..., an]。他们还为题面编写了一个优美而引人入胜的故事，解释了输入的含义、程序应输出什么，并且读起来像一部优秀的犯罪小说。然而，我，海蒂，对此不屑一顾。作为我今天的玩笑，我将故事从题面中移除，并用这两段无用的段落取而代之。现在，去解这个题吧，傻瓜们！输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2200]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（#cf_span[1 ≤ ai ≤ 104]）。请输出一个数。 ## Input 输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2200]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an]（#cf_span[1 ≤ ai ≤ 104]）。 ## Output 请输出一个数。 [samples]

Given: - Integers $ n, k $ such that $ 1 \leq k \leq n \leq 2200 $. - A sequence $ a = (a_1, a_2, \dots, a_n) $ of positive integers with $ 1 \leq a_i \leq 10^4 $. Objective: Output the maximum possible sum of $ k $ non-overlapping contiguous subarrays of $ a $.

Samples

Input #1

8 5
1 1 1 1 1 1 1 1

Output #1

Input #2

10 3
16 8 2 4 512 256 32 128 64 1

Output #2

Input #3

5 1
20 10 50 30 46

Output #3

Input #4

6 6
6 6 6 6 6 6

Output #4

Input #5

1 1
100

Output #5

API Response (JSON)

{
  "problem": {
    "name": "M. April Fools' Problem (easy)",
    "description": {
      "content": "The marmots have prepared a very easy problem for this year's HC2 – this one. It involves numbers _n_, _k_ and a sequence of _n_ positive integers _a_1, _a_2, ..., _a__n_. They also came up with a bea",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF802M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The marmots have prepared a very easy problem for this year's HC2 – this one. It involves numbers _n_, _k_ and a sequence of _n_ positive integers _a_1, _a_2, ..., _a__n_. They also came up with a bea...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "土拨鼠为今年的 HC#cf_span[2] 准备了一个非常简单的题目——就是这个。它涉及数字 #cf_span[n]、#cf_span[k] 和一个由 #cf_span[n] 个正整数组成的序列 #cf_span[a1, a2, ..., an]。他们还为题面编写了一个优美而引人入胜的故事，解释了输入的含义、程序应输出什么，并且读起来像一部优秀的犯罪小说。\n\n然而，我，海蒂，对此不屑一顾。作为我今...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:  \n- Integers $ n, k $ such that $ 1 \\leq k \\leq n \\leq 2200 $.  \n- A sequence $ a = (a_1, a_2, \\dots, a_n) $ of positive integers with $ 1 \\leq a_i \\leq 10^4 $.  \n\nObjective:  \nOutput the maxim...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments