oj.uz

Submission #756781

# Submission time Handle Problem Language Result Execution time Memory
756781 2023-06-12T07:44:53 Z tibinyte Exam (eJOI20_exam) C++17
0 / 100
 7 ms 1068 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
int dp[maxn + 1][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])
        {
            dp[i][i] = 1;
        }
    }
    for (int lg = 2; lg <= n; ++lg)
    {
        for (int st = 1; st + lg - 1 <= n; ++st)
        {
            int dr = st + lg - 1;
            for (int split = st; split <= dr; ++split)
            {
                if (l[split] >= st || r[split] <= dr)
                {
                    int rep = 1;
                    if (split != st)
                    {
                        rep += dp[st][split - 1];
                    }
                    if (split != dr)
                    {
                        rep += dp[split + 1][dr];
                    }
                    dp[st][dr] = max(dp[st][dr], rep);
                }
            }
        }
    }
    cout << dp[1][n];
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -