oj.uz

Submission #756770

# Submission time Handle Problem Language Result Execution time Memory
756770 2023-06-12T07:40:03 Z tibinyte Exam (eJOI20_exam) C++17
30 / 100
 793 ms 31476 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 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 Correct 0 ms 340 KB Output is correct
2 Runtime error 13 ms 520 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 1620 KB Output is correct
9 Correct 47 ms 8228 KB Output is correct
10 Correct 552 ms 31476 KB Output is correct
11 Correct 710 ms 28236 KB Output is correct
12 Correct 672 ms 26552 KB Output is correct
13 Correct 793 ms 26732 KB Output is correct
14 Correct 792 ms 28620 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Runtime error 13 ms 520 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -