Dãy con lượn sóng

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

constexpr int N = 1e4 + 5;
constexpr ll mod = 2019;

int n, m;
int a[N], b[N], last[N], pre[N];
int16_t dp[N][N][2], cnt[N][N][2];

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
}

void Solve()
{
    // Prepare last

    for (int i = 1; i <= n; ++i)
    {
        last[i] = pre[b[i]];
        pre[b[i]] = i;
    }

    // Proccess

    int res(0), amount(0);

    for (int i = 1; i <= m; ++i)
        for (int j = 1, ans[2] = {0, 0}, dem[2] = {1, 1}; j <= n; ++j)
        {
            // t == 0
            {
                dp[i][j][0] = dp[i - 1][j][0];
                cnt[i][j][0] = cnt[i - 1][j][0];

                if (b[j] < a[i])
                {
                    if (ans[0] < dp[i - 1][j][1])
                    {
                        ans[0] = dp[i - 1][j][1];
                        dem[0] = cnt[i - 1][j][1];
                    }
                    else if (ans[0] == dp[i - 1][j][1])
                    {
                        dem[0] += cnt[i - 1][j][1];
                        if (last[j] > 0 && dp[i - 1][j][1] == dp[i - 1][last[j]][1])
                            dem[0] -= cnt[i - 1][last[j]][1];

                        dem[0] %= mod;
                    }
                }
                else if (b[j] == a[i])
                {
                    dp[i][j][0] = ans[0] + 1;
                    cnt[i][j][0] = dem[0];
                }
            }

            // t == 1
            {
                dp[i][j][1] = dp[i - 1][j][1];
                cnt[i][j][1] = cnt[i - 1][j][1];

                if (b[j] > a[i])
                {
                    if (ans[1] < dp[i - 1][j][0])
                    {
                        ans[1] = dp[i - 1][j][0];
                        dem[1] = cnt[i - 1][j][0];
                    }
                    else if (ans[1] == dp[i - 1][j][0])
                    {
                        dem[1] += cnt[i - 1][j][0];
                        if (last[j] > 0 && dp[i - 1][j][0] == dp[i - 1][last[j]][0])
                            dem[1] -= cnt[i - 1][last[j]][0];

                        dem[1] %= mod;
                    }
                }
                else if (b[j] == a[i])
                {
                    dp[i][j][1] = ans[1] + 1;
                    cnt[i][j][1] = dem[1];
                }
            }
        }

    for (int j = 1; j <= n; ++j)
        for (int t = 0; t < 2; ++t)
        {
            if (res < dp[m][j][t])
            {
                res = dp[m][j][t];
                amount = cnt[m][j][t];
            }
            else if (res == dp[m][j][t])
            {
                amount += cnt[m][j][t];

                if (last[j] > 0 && dp[m][j][t] == dp[m][last[j]][t])
                    amount -= cnt[m][last[j]][t];

                amount %= mod;
            }
        }

    cout << res << "\n"
         << (amount + mod) % mod;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}