oj.uz

Submission #667211

# Submission time Handle Problem Language Result Execution time Memory
667211 2022-11-30T18:19:28 Z illyakr Exam (eJOI20_exam) C++14
39 / 100
 1000 ms 33396 KB 
//#pragma GCC optimize("inline,Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,avx,abm")
#include <bits/stdc++.h>
#define ll long long
#define int ll
typedef long double ld;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define y0 dfgoert
#define y1 kjsjofd
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const long long INF1e9 = 1010101010;
const long long INF1e18 = 1010101010101010101;
const long long INF1e15 = 1010101010101010;
const ld PI = 3.14159265358979323846264338327950288419716939937510;

int n;
int a[101010];
int b[101010];
int dp[501010];
int sh[5010][5010];

bool block2 = true;
bool block3 = true;
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    for (int i = 1; i <= n; i++) {
        if (b[i] != b[1]) {block2 = false;break;}
    }
    for (int i = 2; i <= n; i++) {
        if (a[i - 1] >= a[i]) {block3 = false;break;}
    }

    if (block2) {
        int mx = 0;
        int ans = 0, l = 1;
        for (int i = 1; i <= n; i++) {
            if (a[i] > b[i]) {
                if (mx == b[i])
                    ans += (i - l);
                l = i + 1;
                mx = a[i + 1];
                continue;
            }
            mx = max(mx, a[i]);
        }
        if (mx == b[n])
            ans += (n - l + 1);

        cout << ans;
        return;
    }
    if (block3) {
        dp[1] = (a[1] == b[1]);
        for (int i = 2; i <= n; i++) {
            int cnt = 0;
            for (int j = i; j >= 1; j--) {
                cnt += (a[i] == b[j]);
                dp[i] = max(dp[i], dp[j - 1] + cnt);
            }
            for (int j = 1; j <= i; j++) {
                dp[j] = max(dp[j], dp[j - 1] + (a[i] == b[j]));
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans = max(ans, dp[i]);
        cout << ans;
        return;
    }
    for (int i = 1; i <= n; i++)
        sh[i][i] = (a[i] == b[i]);
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            int cnt = 0;
            int MX = 0;
            int moment = l;
            for (int j = r; j >= l; j--) {
                MX = max(MX, a[j]);

                if (MX <= a[r]) {
                    cnt += (a[r] == b[j]);
                    moment = j;
                }
                sh[l][r] = max(sh[l][r], sh[l][j - 1] + cnt);
            }
            for (int j = moment; j <= r; j++) {
                sh[l][j] = max(sh[l][j], sh[l][j - 1] + (a[r] == b[j]));
            }



            cnt = 0;
            MX = 0;
            moment = r;
            for (int j = l; j <= r; j++) {
                MX = max(MX, a[j]);

                if (MX <= a[l]) {
                    cnt += (a[l] == b[j]);
                    moment = j;
                }
                sh[l][r] = max(sh[l][r], sh[j + 1][r] + cnt);
            }
            for (int j = moment; j >= l; j--) {
                sh[j][r] = max(sh[j][r], sh[j + 1][r] + (a[l] == b[j]));
            }
        }
    }
    cout << sh[1][n];
}

int32_t main() {
//    fast
    int t = 1;
//    cin >> t;
    for (int id = 1; id <= t; id++) {
        solve();
    }
    return 0;
}
/**
4
10 1 9 1
10 9 10 9
*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 15 ms 596 KB Output is correct
3 Correct 43 ms 1612 KB Output is correct
4 Correct 29 ms 1868 KB Output is correct
5 Correct 74 ms 1740 KB Output is correct
6 Correct 24 ms 1744 KB Output is correct
7 Correct 29 ms 1868 KB Output is correct
8 Correct 70 ms 1772 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 59 ms 420 KB Output is correct
5 Correct 63 ms 428 KB Output is correct
6 Correct 64 ms 416 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 33396 KB Time limit exceeded
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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 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 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Incorrect 2 ms 724 KB Output isn't correct
10 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 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 212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 59 ms 420 KB Output is correct
11 Correct 63 ms 428 KB Output is correct
12 Correct 64 ms 416 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Incorrect 2 ms 724 KB Output isn't correct
16 Halted 0 ms 0 KB -