oj.uz

Submission #756767

# Submission time Handle Problem Language Result Execution time Memory
756767 2023-06-12T07:39:07 Z tibinyte Exam (eJOI20_exam) C++14
14 / 100
 38 ms 4368 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
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 1 ms 212 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct

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 Correct 0 ms 340 KB Output is correct
2 Runtime error 10 ms 612 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 8 ms 1236 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 2 ms 956 KB Output is correct
9 Correct 38 ms 4368 KB Output is correct
10 Runtime error 1 ms 440 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

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