Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1107 (Div. 3)
G. Summmon Finished
time limit per test: 4 seconds
memory limit per test: 256 megabytes → Virtual participation
Note that the answer for this problem might not fit in int64 or long long. It is Virtual contest is a way to take part in past
contest, as close as possible to participation
recommended to use int128. on time. It is supported only ICPC mode for
virtual contests. If you've seen these
For any array b of length m, define f (b) as the minimum possible value of problems, a virtual contest is not for you -
solve these problems in the archive. If you
max(b) − min(b) that can be achieved by performing the following operation any number of
just want to solve some problem from a
times: contest, a virtual contest is not for you -
solve this problem in the archive. Never use
someone else's code, read the tutorials or
Choose any index 1 ≤ i < m , and do exactly one of the following: communicate with other person during a
virtual contest.
1. Set bi+1 := bi+1 + bi ,
Start virtual contest
2. Set bi+1 := bi+1 − bi .
You are given an array a of length n. Your task is to compute the sum of f over all the
subarrays∗ of a. More formally, determine the value of → Problem tags
∑ f ([al , al+1 , … , ar ]). binary search data structures greedy
1≤l≤r≤n
implementation math number theory
No tag edit access
∗
An array b is a subarray of an array a if b can be obtained from a by deletion of several (possibly, zero or all)
elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is
a subarray of itself.
→ Contest materials
Input
The first line contains a single integer t (1 ≤ t ≤ 10
4
) — the number of test cases. Announcement (en)
Description of each test case follows.
Tutorial (en)
The first line of each test case contains a single integer n (1
5
≤ n ≤ 2 ⋅ 10 ) — the length of
the array a.
9
The second line of each test case contains n integers a1 , a2 , … , an (1 ≤ ai ≤ 10 ) — the
elements of the array a.
5
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 .
Output
For each test case, print a single integer — the value of ∑1≤l≤r≤n f ([al , al+1 , … , ar ]) .
Example
input Copy
5
3
6 4 8
4
1 2 3 4
9
9 9 8 2 4 4 3 5 3
6
18 12 24 9 6 36
6
36 24 18 12 9 6
output Copy
4
3
39
72
111
Note
For the first test case, let us look at all subarrays.
For the single-element subarrays [6] , [4] , and [8] , no operation can change anything, so
each of them contributes 0.
For [6, 4], the first element is fixed as 6. The second element can only be changed to
4 + 6 = 10 or 4 − 6 = −2 , so the gap would become 4 or 8. Hence, doing no
operation is best, and the contribution is 2.
For [4, 8], we choose i = 1 and apply b2 := b2 − b1 . Then the subarray becomes
[4, 4] , so its contribution is 0.
For [6, 4, 8], we keep the first two elements as they are and choose i = 2. Then we
apply b3 := b3 − b2 , so 8 becomes 4. The array becomes [6, 4, 4], and therefore
max(b) − min(b) = 6 − 4 = 2 . It can be shown that this is the optimal value.
Therefore, the answer for the first test case is 0 + 0 + 0 + 2 + 0 + 2 = 4 .
For the second test case, every subarray of length 1 contributes 0. Among the remaining
subarrays, only [2, 3], [3, 4], and [2, 3, 4] have a non-zero contribution, each contributing 1.
Therefore, the answer is 1 + 1 + 1 = 3.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jul/03/2026 14:56:11UTC+5.5 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by