Codeforces Solution-C. Three Parts of the Array-Solution in C, C++, Java, Python

Algorithm

You are given an array $d_{1}, d_{2}, \dots, d_{n}$ consisting of $n$ integer numbers.

Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array.

Let the sum of elements of the first part be $s u m_{1}$ , the sum of elements of the second part be $s u m_{2}$ and the sum of elements of the third part be $s u m_{3}$ . Among all possible ways to split the array you have to choose a way such that $s u m_{1} = s u m_{3}$ and $s u m_{1}$ is maximum possible.

More formally, if the first part of the array contains $a$ elements, the second part of the array contains $b$ elements and the third part contains $c$ elements, then:

s u m 1 = \sum 1 \leq i \leq a d i,

s u m 2 = \sum a + 1 \leq i \leq a + b d i,

s u m 3 = \sum a + b + 1 \leq i \leq a + b + c d i .

The sum of an empty array is $0$ .

Your task is to find a way to split the array such that $s u m_{1} = s u m_{3}$ and $s u m_{1}$ is maximum possible.

Input

The first line of the input contains one integer $n$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ) — the number of elements in the array $d$ .

The second line of the input contains $n$ integers $d_{1}, d_{2}, \dots, d_{n}$ ( $1 \leq d_{i} \leq 10^{9}$ ) — the elements of the array $d$ .

Output

Print a single integer — the maximum possible value of $s u m_{1}$ , considering that the condition $s u m_{1} = s u m_{3}$ must be met.

Obviously, at least one valid way to split the array exists (use $a = c = 0$ and $b = n$ ).

Examples
input
Copy
5
1 3 1 1 4
output
Copy
5
input
Copy
5
1 3 2 1 4
output
Copy
4
input
Copy
3
4 1 2
output
Copy
0

Note

In the first example there is only one possible splitting which maximizes $s u m_{1}$ : $[1, 3, 1], [], [1, 4]$ .

In the second example the only way to have $s u m_{1} = 4$ is: $[1, 3], [2, 1], [4]$ .

In the third example there is only one way to split the array: $[], [4, 1, 2], []$ .

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, a[N];
long long cs[N];

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i)
    cin >> a[i];
  
  for(int i = 1; i <= n; ++i)
    cs[i] = cs[i - 1] + a[i - 1];
  
  long long res = 0;
  for(int i = n, idx; i >= 1; --i) {
    long long cur = cs[n] - cs[i - 1];

    idx = lower_bound(cs, cs + n - (n - i + 1), cur) - cs;
    if(cs[idx] == cur)
      res = max(res, cur);
  }

  cout << res << endl;

  return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

5
1 3 1 1 4

Output

–

cmd

Demonstration

Codeforces Solution-C. Three Parts of the Array-Solution in C, C++, Java, Python,Three Parts of the Array,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 3 years ago 1049 0