← 返回题目列表

Codeforces · 2079/B

B. 算术练习

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Arithmetic Exercise - 原题 PDF 第 1 页
原题PDF第4页
Arithmetic Exercise - 原题 PDF 第 2 页
原题PDF第5页
可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. First day
                                  Moscow, March 7th, 2025
Problem Stone. The arithmetic exercise

     Input file:         input.txt or standard input
    Output file:       output.txt or standard output
    Time limit:        2 seconds
    Memory limit:     256 megabytes

Oleg and Dasha participated in a team competition, but unfortunately, they were unable to solve any
problems. Oleg immediately realized that their team wasn’t training enough. Then, their mutual friend
suggested an interesting exercise. The exercise was quite simple, and to solve it, they only needed to know
the rules of addition and subtraction of integers.

You are given an array a of length n, where initially all values are zero. You are also given m numbers
x1, x2,  . . . xm. Then, for each i from 1 to m, you choose some index ji and make the change aji = xi−aji.
Help Oleg and Dasha determine what the maximum possible sum of the elements of array a can be after
all the changes, if the choices are made optimally.

Input

Each test consists of several input data sets. The first line contains a single integer t (1 ≤t ≤10 000) —
the number of input data sets. Then follows the description of the data sets.

The first line of each data set contains two integers n and m (1 ≤n, m ≤300 000) — the length of the
array a and the number of values xi, respectively.
The second line of each data set contains m integers x1, x2, . . ., xm (−109 ≤xi ≤109) — the description
of the values.

Let N be the sum of n over all data sets, and M be the sum of m over all data sets.

It is guaranteed that N and M do not exceed 300 000.

Output

For each data set, output a single number on a new line — the maximum sum of the array a that can be
obtained.

Example

                  input                                   output
 4                                       2
 1 4                                     18
 1 2 3 4                                 1085
 2 7                                     17
 10 3 7 1 4 6 3
 4 10
 103 354 1 227 179 189 142 201 165 140
 5 3
 -10 11 -4

Note

In the first data set, all operations are applied to the first element of the array a. It sequentially becomes
1 −0 = 1, 2 −1 = 1, 3 −1 = 2, 4 −2 = 2, so the answer is 2.

In the second data set, the following sequence of changes can be performed:


   1. Apply the change to the first element: a1 = 10 −a1 = 10 −0 = 10, a = [10, 0].

   2. Apply the change to the first element: a1 = 3 −a1 = 3 −10 = −7, a = [−7, 0].


                                         Page 4 of 9

Open Olympiad in Informatics 2024/25. First day
                                  Moscow, March 7th, 2025

   3. Apply the change to the first element: a1 = 7 −a1 = 7 −(−7) = 14, a = [14, 0].

   4. Apply the change to the first element: a1 = 1 −a1 = 1 −14 = −13, a = [−13, 0].

   5. Apply the change to the second element: a2 = 4 −a2 = 4 −0 = 4, a = [−13, 4].

   6. Apply the change to the first element: a1 = 6 −a1 = 6 −(−13) = 19, a = [19, 4].

   7. Apply the change to the second element: a2 = 3 −a2 = 3 −4 = −1, a = [19, −1].


At the end, we have a = [19, −1], so the final sum is 18.

It can be shown that a better result is not possible.

Scoring

The tests for this problem consist of ten groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Please note that passing the example tests is not
required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.

                               Additional constraints           Required
    Group  Points                                              Comment
                                                        Groups                         n, N      m, M             xi

       0       0        –          –             –             –          Examples.

       1       4        –          –           0 ≤xi          –         All xi are same

                M ≤30
       2       8     n = 2                      –             –
                  m ≤18

       3      11     n = 2   M ≤50    −10 ≤xi ≤10       –

       4       9     n = 2  M ≤400  −400 ≤xi ≤400      3

             N ≤30  M ≤30
       5       8                                 –             0
                  n ≤18   m ≤18

       6      10  N ≤2000 M ≤2000       0 ≤xi          –

       7      12  N ≤2000 M ≤2000         –             0, 2 – 6

                                                                    There are no more
       8      10        –          –           0 ≤xi          1       than two different
                                                                                 values among xi

       9      17        –          –           0 ≤xi           1, 6, 8

      10      11        –          –             –           0 – 9    Offline-evaluation.





                                         Page 5 of 9