/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
/**
* @brief Calculate minimum operations to make array "great"
* @param a the array (0-indexed)
* @param n length of the array
* @return minimum number of operations
*/
long long min_operations_to_great_array(long long *a, int n) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int n;
scanf("%d", &n);
// Use 0-indexed array
long long *a = (long long *)malloc(n * sizeof(long long));
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
long long result = min_operations_to_great_array(a, n);
printf("%lld\n", result);
free(a);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Make the Array Great
You are given an array $A[0..n-1]$ of $n$ non-negative integers (0-indexed). An array is called **great** if for every contiguous subarray of length at least 2, the sum of elements at odd positions (in the original array) is greater than or equal to the sum of elements at even positions (in the original array).
Formally, an array $A[0..n-1]$ is great if and only if: for every contiguous subarray $A[l..r]$ where $r - l + 1 \geq 2$, we have:
$$\sum_{\substack{i=l \\ i \text{ odd}}}^{r} A[i] \geq \sum_{\substack{i=l \\ i \text{ even}}}^{r} A[i]$$
where positions 0, 2, 4, ... are even and positions 1, 3, 5, ... are odd.
**Examples:**
- $[3, 8, 4, 4]$ is a great array
- $[2, 3, 1, 4, 2]$ is a great array
- $[0, 2, 4, 1]$ is **NOT** a great array
For the array $[0, 2, 4, 1]$ (0-indexed), consider the subarray $A[1..3] = [2, 4, 1]$:
- Even positions sum: $A[2] = 4$
- Odd positions sum: $A[1] + A[3] = 2 + 1 = 3$
- Since $3 < 4$, the condition is violated.
In one operation, you can decrease any element by 1 (but not below 0). Find the minimum number of operations needed to make the array great.
### Input
- First line contains a single integer $n$ ($1 \leq n \leq 10^6$): the length of the array
- Second line contains $n$ non-negative integers representing the array ($0 \leq A[i] \leq 10^5$)
### Output
Output a single integer: the minimum number of operations needed to make the array great.
**Note:** The total number of operations may exceed the range of a 32-bit signed integer. Please use `long long` in C to avoid overflow.
### Example
**Input**
```
4
0 2 4 1
```
**Output**
```
3
```
**Explanation**
Original array: $A = [0, 2, 4, 1]$
By decreasing $A[2]$ from 4 to 1 (3 operations), we get $A' = [0, 2, 1, 1]$.
Now, for any subarray $A'[l..r]$ ($r-l+1 \geq 2$), the condition holds. For example, in $A'[1..3] = [2, 1, 1]$:
- Odd sum: $A'[1]+A'[3] = 2+1=3$.
- Even sum: $A'[2]=1$.
- $3 \geq 1$, condition satisfied.
It can be proven that the minimum number of operations required is 3.