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


可复制的 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