9/13/25, 4:11 AM Problem - C - Codeforces
Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 1045 (Div. 2)
C. Even Larger Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Practice?
An array is called good if, for every subarray of length at least 2, the sum of the elements at
∗
Want to solve the contest problems after the
official contest ends? Just register for
even indices (with respect to the original array) is greater than or equal to the sum of the practice and you will be able to submit
elements at odd indices. Array indexing starts from 1. solutions.
For example, the arrays [3, 8, 4, 4] and [2, 3, 1, 4, 2] are good. The array [0, 2, 4, 1] is not Register for practice
because, in the subarray [2, 4, 1], the elements at even indices in the original array are 2 (index
2) and 1 (index 4), while the only element at an odd index is 4 (index 3). Since 2 + 1 < 4 , the
condition does not hold for this subarray. → Virtual participation
You are given an array of n non-negative integers a1 , a2 , … , an . In one operation, you can Virtual contest is a way to take part in past
contest, as close as possible to participation
decrease any element in the array by 1, but all elements must remain non-negative. Your task is on time. It is supported only ICPC mode for
to find the minimum number of operations needed to make the array a good. It can be proved virtual contests. If you've seen these
problems, a virtual contest is not for you -
that it is possible to make the array good using a finite number of operations. solve these problems in the archive. If you
just want to solve some problem from a
∗
An array b is a subarray of an array a if b can be obtained from a by the deletion of several (possibly, zero or all) contest, a virtual contest is not for you -
solve this problem in the archive. Never use
elements from the beginning and several (possibly, zero or all) elements from the end.
someone else's code, read the tutorials or
Input communicate with other person during a
virtual contest.
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 10
4
). The description of the test cases follows. Start virtual contest
The first line of each test case contains a single integer n (2 ≤ n ≤ 2 ⋅ 10
5
) — the length of the
array a. → Problem tags
The second line of each test case contains n non-negative integers a1 , a2 , … , an ( brute force greedy implementation
9
0 ≤ ai ≤ 10 ) — the elements of the array a .
*1200
5 No tag edit access
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 .
Output → Contest materials
For each test case, output a single integer in a new line — the minimum number of operations
needed to make the array a good.
Announcement (en)
Example Tutorial (en)
input Copy
8
4
3 8 4 4
4
0 2 3 5
2
3 1
5
2 3 1 4 2
4
0 2 4 1
5
3 1 4 5 1
11
3 0 5 4 4 5 3 0 3 4 1
12
410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354
801228787 44181004 1000000000 3829103
output Copy
0
1
2
0
3
6
14
4450984776
https://codeforces.com/contest/2134/problem/C 1/2
9/13/25, 4:11 AM Problem - C - Codeforces
Note
In the first test case, the array a is already good, so the answer is 0. Below are the checks for
each subarray:
Subarray Even Index Sum Odd Index Sum Condition met?
[3, 8] 8 3 Yes
[8, 4] 8 4 Yes
[4, 4] 4 4 Yes
[3, 8, 4] 8 3 + 4 = 7 Yes
[8, 4, 4] 8 + 4 = 12 4 Yes
[3, 8, 4, 4] 8 + 4 = 12 3 + 4 = 7 Yes
In the second test case, the array a is not good:
Subarray Even Index Sum Odd Index Sum Condition met?
[0, 2] 2 0 Yes
[2, 3] 2 3 No
[3, 5] 5 3 Yes
[0, 2, 3] 2 0 + 3 = 3 No
[2, 3, 5] 2 + 5 = 7 3 Yes
[0, 2, 3, 5] 2 + 5 = 7 0 + 3 = 3 Yes
However, if we perform an operation on index 3, the array becomes [0, 2, 2, 5] and is good now:
Subarray Even Index Sum Odd Index Sum Condition met?
[0, 2] 2 0 Yes
[2, 2] 2 2 Yes
[2, 5] 5 2 Yes
[0, 2, 2] 2 0 + 2 = 2 Yes
[2, 2, 5] 2 + 5 = 7 2 Yes
[0, 2, 2, 5] 2 + 5 = 7 0 + 2 = 2 Yes
Therefore, the answer is 1.
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/13/2025 04:11:07UTC+5.5 (k2).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
https://codeforces.com/contest/2134/problem/C 2/2
