B. Red and Blue SOLUTION Code Forces

B. Red and Blue SOLUTION CodeForces

Monocarp had a sequence aa consisting of n+mn+m integers a1,a2,…,an+ma1,a2,…,an+m. He painted the elements into two colors, red and blue; nn elements were painted red, all other mm elements were painted blue.

After painting the elements, he has written two sequences r1,r2,…,rnr1,r2,…,rn and b1,b2,…,bmb1,b2,…,bm. The sequence rr consisted of all red elements of aa in the order they appeared in aa; similarly, the sequence bb consisted of all blue elements of aa in the order they appeared in aa as well.

Unfortunately, the original sequence was lost, and Monocarp only has the sequences rr and bb. He wants to restore the original sequence. In case there are multiple ways to restore it, he wants to choose a way to restore that maximizes the value off(a)=max(0,a1,(a1+a2),(a1+a2+a3),…,(a1+a2+a3+⋯+an+m))f(a)=max(0,a1,(a1+a2),(a1+a2+a3),…,(a1+a2+a3+⋯+an+m))

Help Monocarp to calculate the maximum possible value of f(a)f(a).Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases. Then the test cases follow. Each test case consists of four lines.

The first line of each test case contains one integer nn (1≤n≤1001≤n≤100).

The second line contains nn integers r1,r2,…,rnr1,r2,…,rn (−100≤ri≤100−100≤ri≤100).

The third line contains one integer mm (1≤m≤1001≤m≤100).

The fourth line contains mm integers b1,b2,…,bmb1,b2,…,bm (−100≤bi≤100−100≤bi≤100).Output

For each test case, print one integer — the maximum possible value of f(a)f(a).

Example

input

4
4
6 -5 7 -3
3
2 3 -4
2
1 1
4
10 -3 2 2
5
-1 -2 -3 -4 -5
5
-1 -2 -3 -4 -5
1
0
1
0

Output

13
13
0
0

Note

  • In the explanations for the sample test cases, red elements are marked as bold.
  • In the first test case, one of the possible sequences aa is [6,2,−5,3,7,−3,−4][6,2,−5,3,7,−3,−4].
  • In the second test case, one of the possible sequences aa is [10,1,−3,1,2,2][10,1,−3,1,2,2].
  • In the third test case, one of the possible sequences aa is [−1,−1,−2,−3,−2,−4,−5,−3,−4,−5][−1,−1,−2,−3,−2,−4,−5,−3,−4,−5].
  • In the fourth test case, one of the possible sequences aa is [0,0][0,0].

Solution

Program C++:

#include <bits/stdc++.h>
#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef long double ld;
using namespace std;
  
const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e5 + 5;
const int md2 = 998244353;
const int md = 1e9 + 7;
 
void solve() {
    ll ans = 0;
    range(i, 2) {
        int n; cin >> n;
        ll x = 0;
        ll res = 0;
        range(j, n) {
            int y; cin >> y;
            x += y;
            res = max(res, x);
        }
        ans += res;
    }
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tests = 1;
    cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

Program Python:

import sys
range = xrange
input = raw_input

t = int(input())
for _ in range(t):
    n = int(input())
    R = [int(x) for x in input().split()]
    m = int(input())
    B = [int(x) for x in input().split()]

    r_cumsum = maxr_cumsum = 0
    for r in R:
        r_cumsum += r
        maxr_cumsum = max(maxr_cumsum, r_cumsum)
    
    b_cumsum = maxb_cumsum = 0
    for b in B:
        b_cumsum += b
        maxb_cumsum = max(maxb_cumsum, b_cumsum)

    print(maxr_cumsum + maxb_cumsum)

RELATED :

Leave a Comment