F. Ilya Muromets

Codeforces

IDCF10051F

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Ilya Muromets is a legendary bogatyr. Right now he is struggling against Zmej Gorynych, a dragon with n heads numbered from 1 to n from left to right. Making one sweep of sword Ilya Muromets can cut at most k contiguous heads of Zmej Gorynych. Thereafter heads collapse getting rid of empty space between heads. So in a moment before the second sweep all the heads form a contiguous sequence again. As we all know, dragons can breathe fire. And so does Zmej Gorynych. Each his head has a firepower. The firepower of the i-th head is fi. Ilya Muromets has time for at most two sword sweeps. The bogatyr wants to reduce dragon's firepower as much as possible. What is the maximum total firepower of heads which Ilya can cut with at most two sword sweeps? The first line contains a pair of integer numbers n and k (1 ≤ n, k ≤ 2·105) — the number of Gorynych's heads and the maximum number of heads Ilya can cut with a single sword sweep. The second line contains the sequence of integer numbers f1, f2, ..., fn (1 ≤ fi ≤ 2000), where fi is the firepower of the i-th head. Print the required maximum total head firepower that Ilya can cut. ## Input The first line contains a pair of integer numbers n and k (1 ≤ n, k ≤ 2·105) — the number of Gorynych's heads and the maximum number of heads Ilya can cut with a single sword sweep. The second line contains the sequence of integer numbers f1, f2, ..., fn (1 ≤ fi ≤ 2000), where fi is the firepower of the i-th head. ## Output Print the required maximum total head firepower that Ilya can cut. [samples]

**Definitions** Let $ s \in \{a, b, \dots, z\}^* $ be the encrypted string, with $ 1 \leq |s| \leq 10^5 $. **Constraints** Each character of $ s $ is a lowercase English letter. **Objective** Output the original (decrypted) string corresponding to $ s $, under an unspecified decryption algorithm.

API Response (JSON)

{
  "problem": {
    "name": "F. Ilya Muromets",
    "description": {
      "content": "Ilya Muromets is a legendary bogatyr. Right now he is struggling against Zmej Gorynych, a dragon with n heads numbered from 1 to n from left to right. Making one sweep of sword Ilya Muromets can cut ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10051F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ilya Muromets is a legendary bogatyr. Right now he is struggling against Zmej Gorynych, a dragon with n heads numbered from 1 to n from left to right.\n\nMaking one sweep of sword Ilya Muromets can cut ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{a, b, \\dots, z\\}^* $ be the encrypted string, with $ 1 \\leq |s| \\leq 10^5 $.\n\n**Constraints**  \nEach character of $ s $ is a lowercase English letter.\n\n**Objective**  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments