符号选择 / opt

Luogu

IDLGB4468

Time1000ms

Memory512MB

DifficultyP1

2025O2优化排序山西数组科创活动小学活动

给定一个包含 $n$ 个自然数的序列 $x_1,x_2,...,x_n$。现在要对序列中的每个数 $x_i$ 赋予一个正号（$+x_i$）或负号（$-x_i$），然后求和。特别的，在 $n$ 个数中，必须 **恰好** 有 $k$ 个数使用正号，其余 $n-k$ 个数使用负号。求这种操作下，得到的 **最大总和** 是多少。 ## Input 第一行包含两个整数 $n$ 和 $k$，分别表示序列的长度和必须选择加号的次数。第二行包含 $n$ 个自然数 $x_1,x_2,...,x_n$，表示给定的序列，保证 $x_1\ge x_2\ge...\ge x_n$。 ## Output 一行，包含一个整数，表示能够得到的最大总和。 [samples] ## Note #### 【数据范围】对于 $20\%$ 的数据，$1\le n\le10$。对于另外 $10\%$ 的数据，$n=k$。对于另外 $10\%$ 的数据，每个 $x_i$ 相等。对于 $100\%$ 的数据，$1\le k\le n\le10^5,0\le x_i\le10^9$。

Samples

Input #1

3 2
5 2 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "符号选择 / opt",
    "description": {
      "content": "给定一个包含 $n$ 个自然数的序列 $x_1,x_2,...,x_n$。 现在要对序列中的每个数 $x_i$ 赋予一个正号（$+x_i$）或负号（$-x_i$），然后求和。 特别的，在 $n$ 个数中，必须 **恰好** 有 $k$ 个数使用正号，其余 $n-k$ 个数使用负号。 求这种操作下，得到的 **最大总和** 是多少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4468"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 $n$ 个自然数的序列 $x_1,x_2,...,x_n$。\n\n现在要对序列中的每个数 $x_i$ 赋予一个正号（$+x_i$）或负号（$-x_i$），然后求和。\n\n特别的，在 $n$ 个数中，必须 **恰好** 有 $k$ 个数使用正号，其余 $n-k$ 个数使用负号。\n\n求这种操作下，得到的 **最大总和** 是多少。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $k$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments