Competitive Programming Solutions

1469B - Red And Blue

28 Dec 2020 — Tags: greedy — URL

$f(a)$ is maximized when $a$ is of the form:

a = r[0, i] . b[0, j] . r[i + 1, n] . b[j + 1, m]

Where . means concatenation and $i$ and $j$ are the indices that maximize their respective prefix sums.

The reason behind is that the sum of a[0... i + j] = r[0, i] . b[0, j] will be a consequently the maximal term of $f(a)$ for all $a$.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi r, vi b)
{
    int n = (int)(r).size(), m = (int)(b).size();
    vi pr(n, 0), pb(m, 0);
    partial_sum(begin(r), end(r), begin(pr));
    partial_sum(begin(b), end(b), begin(pb));
    return max(*max_element(begin(pr), end(pr)), 0) + max(*max_element(begin(pb), end(pb)), 0);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n;
        vi r(n);
        for (auto &x : r)
            cin >> x;
        cin >> m;
        vi b(m);
        for (auto &x : b)
            cin >> x;
        cout << solve(r, b) << endl;
    }
    return 0;
}

Related posts