Submission #756770

#	Time	Username	Problem	Language	Result	Execution time	Memory
756770		tibinyte	Exam (eJOI20_exam)	C++17	30 / 100	793 ms	31476 KiB

exam

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
int dp[maxn + 1][maxn + 1][2 * maxn + 1];
int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
    }
    vector<int> norm;
    for (int i = 1; i <= n; ++i)
    {
        norm.push_back(a[i]);
        norm.push_back(b[i]);
    }
    sort(norm.begin(), norm.end());
    map<int, int> qui;
    int p = 0;
    for (auto i : norm)
    {
        if (qui.find(i) == qui.end())
        {
            qui[i] = ++p;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        a[i] = qui[a[i]];
        b[i] = qui[b[i]];
    }
    vector<int> l(n + 1), r(n + 1, INT_MAX);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j <= n; ++j)
        {
            if (a[j] == b[i])
            {
                r[i] = j;
                break;
            }
            if (a[j] > b[i])
            {
                break;
            }
        }
        for (int j = i; j >= 1; --j)
        {
            if (a[j] == b[i])
            {
                l[i] = j;
                break;
            }
            if (a[j] > b[i])
            {
                break;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] == b[i])
        {
            for (int j = 1; j <= a[i]; ++j)
            {
                dp[i][i][j] = 1;
            }
        }
    }
    for (int lg = 2; lg <= n; ++lg)
    {
        for (int st = 1; st + lg - 1 <= n; ++st)
        {
            int dr = st + lg - 1;
            for (int lim = 1; lim <= n + n; ++lim)
            {
                for (int split = st; split <= dr; ++split)
                {
                    if (b[split] >= lim && (l[split] >= st || r[split] <= dr))
                    {
                        int rep = 1;
                        if (split != st)
                        {
                            rep += dp[st][split - 1][b[split]];
                        }
                        if (split != dr)
                        {
                            rep += dp[split + 1][dr][b[split]];
                        }
                        dp[st][dr][lim] = max(dp[st][dr][lim], rep);
                    }
                }
            }
        }
    }
    cout << dp[1][n][1];
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 16 / 16
• Subtask 6: 0 / 22