Submission #1214295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214295		badge881	Exam (eJOI20_exam)	C++20	100 / 100	130 ms	98604 KiB

exam

#include <bits/stdc++.h>
using namespace std;

long long pie(long long army) { return (1ll << army); }

signed main()
{
    int n;
    scanf("%d", &n);
    int A[n], B[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &B[i]);
    int us[n + 1];
    int nex = 2, bin = 0;
    for (int i = 1; i <= n; i++)
    {
        us[i] = bin;
        if (nex == i)
        {
            bin++;
            nex <<= 1;
        }
    }
    int spar[us[n] + 1][n];
    for (int i = 0; i < n; i++)

        spar[0][i] = A[i];

    for (int i = 1; i <= us[n]; i++)

        for (int j = 0; j <= n - pie(i); j++)

            spar[i][j] = max(spar[i - 1][j], spar[i - 1][j + pie(i - 1)]);

    if (n > 5000)
    {
        bool b = true;
        for (int i = 1; i < n; i++)
            if (B[i] != B[i - 1])
            {
                b = false;
                break;
            }
        if (b)
        {
            bool dp[n + 1];
            for (bool &x : dp)
                x = false;
            bool cur = false;
            for (int i = 0; i < n; i++)
            {
                if (A[i] == B[0])
                    cur = true;
                if (A[i] > B[0])
                    cur = false;
                dp[i] |= cur;
            }
            cur = false;
            for (int i = n - 1; i >= 0; i--)
            {
                if (A[i] == B[0])
                    cur = true;
                if (A[i] > B[0])
                    cur = false;
                dp[i] |= cur;
            }
            int ans = 0;
            for (int i = 0; i < n; i++)
                if (dp[i])
                    ans++;
            cout << ans;
            return 0;
        }
        else
        {
            map<int, int> mp;
            for (int i = 1; i <= n; i++)
                mp[A[i - 1]] = i;
            vector<int> v;
            for (int i = 0; i < n; i++)
            {
                int j = mp[B[i]];
                if (j)
                {
                    j--;
                    int boy = abs(i - j) + 1;
                    int mx = max(spar[us[boy]][min(i, j)], spar[us[boy]][max(i, j) - pie(us[boy]) + 1]);
                    if (mx <= B[i])
                        v.push_back(j + 1);
                }
            }
            vector<int> ans;
            for (int x : v)
            {
                int l = 0, r = ans.size();
                while (l < r)
                {
                    int m = (l + r) / 2;
                    if (ans[m] <= x)
                        l = m + 1;
                    else
                        r = m;
                }
                if (l == ans.size())
                    ans.push_back(x);
                else
                    ans[l] = x;
            }
            cout << ans.size();
            return 0;
        }
    }
    int dp[n + 1][n + 1];
    for (auto &x : dp)
        for (auto &y : x)
            y = -1;
    dp[0][0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (dp[i][j] == -1)
                continue;
            if (A[j] == B[i])
            {
                int boy = abs(i - j) + 1;
                int mx = max(spar[us[boy]][min(i, j)], spar[us[boy]][max(i, j) - pie(us[boy]) + 1]);
                if (mx <= B[i])
                {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
                    continue;
                }
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
        }
        if (dp[i][n] != -1)
            dp[i + 1][n] = max(dp[i + 1][n], dp[i][n]);
    }
    for (int i = 0; i < n; i++)
        if (dp[n][i] != -1)
            dp[n][i + 1] = max(dp[n][i + 1], dp[n][i]);
    cout << dp[n][n];
}

Compilation message (stderr)

exam.cpp: In function 'int main()':
exam.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
exam.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
exam.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d", &B[i]);
      |         ~~~~~^~~~~~~~~~~~~

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