F. Array Covering

Codeforces

IDCF720F

Time3000ms

Memory256MB

Difficulty—

data structures

English · Original

Chinese · Translation

Formal · Original

Misha has an array of integers of length _n_. He wants to choose _k_ different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays. Misha wants to choose the subarrays in such a way that if he calculated the sum of elements for each subarray, and then add up all these sums, the resulting value was maximum possible. ## Input The first line of input contains two integers: _n_, _k_ (1 ≤ _n_ ≤ 100 000, 1 ≤ _k_ ≤ _n_·(_n_ + 1) / 2) — the number of elements in the array and the number of different subarrays that must be chosen. The second line contains _n_ integers _a__i_ ( - 50 000 ≤ _a__i_ ≤ 50 000) — the elements of the array. ## Output Output one integer — the maximum possible value Misha can get by choosing _k_ different subarrays. [samples]

Misha 有一个长度为 $n$ 的整数数组。他希望选择 $k$ 个不同的连续子数组，使得数组中的每个元素至少属于其中一个被选中的子数组。 Misha 希望以这样的方式选择子数组：如果他计算每个子数组的元素和，然后将所有这些和相加，得到的值尽可能大。输入的第一行包含两个整数：$n$, $k$（$1 ≤ n ≤ 100 000$, $1 ≤ k ≤ n·(n + 1) / 2$）— 分别表示数组中元素的个数和必须选择的不同子数组的个数。第二行包含 $n$ 个整数 $a_i$（$ - 50 000 ≤ a_i ≤ 50 000$）— 数组的元素。请输出一个整数 —— Misha 通过选择 $k$ 个不同子数组所能获得的最大可能值。 ## Input 输入的第一行包含两个整数：$n$, $k$（$1 ≤ n ≤ 100 000$, $1 ≤ k ≤ n·(n + 1) / 2$）— 分别表示数组中元素的个数和必须选择的不同子数组的个数。第二行包含 $n$ 个整数 $a_i$（$ - 50 000 ≤ a_i ≤ 50 000$）— 数组的元素。 ## Output 请输出一个整数 —— Misha 通过选择 $k$ 个不同子数组所能获得的最大可能值。 [samples]

Let $ a = [a_1, a_2, \dots, a_n] $ be an array of integers. Let $ \mathcal{S} $ be the set of all contiguous subarrays of $ a $, i.e., $$ \mathcal{S} = \{ [a_i, a_{i+1}, \dots, a_j] \mid 1 \leq i \leq j \leq n \}. $$ For any subarray $ s = [a_i, \dots, a_j] $, define its sum as $$ \text{sum}(s) = \sum_{\ell=i}^j a_\ell. $$ We are to select a subset $ \mathcal{T} \subseteq \mathcal{S} $ of exactly $ k $ distinct subarrays such that: - Every element $ a_i $ (for $ 1 \leq i \leq n $) is covered by at least one subarray in $ \mathcal{T} $, i.e., $$ \bigcup_{s \in \mathcal{T}} s = \{a_1, a_2, \dots, a_n\}. $$ The goal is to maximize: $$ \sum_{s \in \mathcal{T}} \text{sum}(s). $$ --- **Formal Problem Statement:** Given integers $ n, k $ and array $ a \in \mathbb{Z}^n $, find $$ \max_{\substack{\mathcal{T} \subseteq \mathcal{S} \\ |\mathcal{T}| = k \\ \bigcup_{s \in \mathcal{T}} s = [n]}} \sum_{s \in \mathcal{T}} \text{sum}(s), $$ where $ [n] = \{1, 2, \dots, n\} $, and each $ s \in \mathcal{S} $ is a contiguous subarray.

Samples

Input #1

5 4
6 -4 -10 -4 7

Output #1

API Response (JSON)

{
  "problem": {
    "name": "F. Array Covering",
    "description": {
      "content": "Misha has an array of integers of length _n_. He wants to choose _k_ different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays. Misha wants to ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF720F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Misha has an array of integers of length _n_. He wants to choose _k_ different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays.\n\nMisha wants to ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Misha 有一个长度为 $n$ 的整数数组。他希望选择 $k$ 个不同的连续子数组，使得数组中的每个元素至少属于其中一个被选中的子数组。\n\nMisha 希望以这样的方式选择子数组：如果他计算每个子数组的元素和，然后将所有这些和相加，得到的值尽可能大。\n\n输入的第一行包含两个整数：$n$, $k$（$1 ≤ n ≤ 100 000$, $1 ≤ k ≤ n·(n + 1) / 2$）— 分别表示数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of integers.\n\nLet $ \\mathcal{S} $ be the set of all contiguous subarrays of $ a $, i.e.,  \n$$\n\\mathcal{S} = \\{ [a_i, a_{i+1}, \\dots, a_j] \\mid 1 \\leq i \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments