1519D - Maximum Sum of Products - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define pb push_back
using namespace std;
const ll N = 5e3+2;
const ll MOD = 1e9 + 7;
ll n;
vector<vector<ll>> dp;
vector<vector<bool>> test[2];
vector<ll> a, b;
ll solve(ll i, ll j, bool state)
{
    if(i==n)
    {
        if(j==n)
            return 0;
        else
            return solve(i-1,j,false);
    }
    if(test[state][i][j]) return dp[i][j];
    ll ans = 0;
    if(!state)
    {
        if(i==j)
            ans = a[i]*b[j] + solve(i+1,j+1,false);
        else
        {
            ans = a[i]*b[j] + a[j]*b[i];
            if(i-1==j+1)
                ans += a[i-1]*b[j+1];
            if(i-1>j+1)
                ans += solve(i-1,j+1,false);
        }
    }
    else
    {
        if(i==j)
            ans = max(a[i]*b[j]+solve(i+1,j+1,true),solve(i+1,j,true));
        else
        {
            ans = solve(i+1,j,true);
            ll ans1 = a[i]*b[j] + a[j]*b[i];
            if(i-1==j+1)
                ans1 += a[i-1]*b[j+1];
            if(i-1>j+1)
                ans1 += solve(i-1,j+1,false);
            ans1 += solve(i+1,i+1,false);
            ans = max(ans, ans1);
        }
    }
    test[state][i][j] = true;
    return dp[i][j] = max(dp[i][j],ans);
}

int main()
{
    fastread();
    cin>>n;
    a.assign(n,0);
    b.assign(n,0);
    dp.assign(n,vector<ll>(n,-1));
    test[0].assign(n,vector<bool>(n,0));
    test[1].assign(n,vector<bool>(n,0));
    for(ll i = 0; i<n; i++)
        cin>>a[i];
    for(ll i = 0; i<n; i++)
        cin>>b[i];
    ll ans = solve(0,0, true);
    cout<<ans<<"\n";
    return 0;
}
/*
*/