oj.uz

Submission #667213

# Submission time Handle Problem Language Result Execution time Memory
667213 2022-11-30T18:28:02 Z illyakr Exam (eJOI20_exam) C++14
39 / 100
 1000 ms 33480 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]));
            }
        }
    }
    int ans = 0;
    for (int l = 1; l <= n; l++) {
        for (int r = 1; r <= n; r++) {
            ans = max(ans, sh[l][r]);
        }
    }
    cout << ans;
}

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 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 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 608 KB Output is correct
3 Correct 43 ms 1612 KB Output is correct
4 Correct 26 ms 1820 KB Output is correct
5 Correct 72 ms 1804 KB Output is correct
6 Correct 27 ms 1848 KB Output is correct
7 Correct 30 ms 1816 KB Output is correct
8 Correct 69 ms 1764 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 57 ms 424 KB Output is correct
5 Correct 61 ms 420 KB Output is correct
6 Correct 63 ms 340 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 33480 KB Time limit exceeded
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 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 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 Correct 0 ms 468 KB Output is correct
9 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 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 57 ms 424 KB Output is correct
11 Correct 61 ms 420 KB Output is correct
12 Correct 63 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Incorrect 1 ms 724 KB Output isn't correct
16 Halted 0 ms 0 KB -