oj.uz

답안 #667214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667214 2022-11-30T18:30:03 Z illyakr Exam (eJOI20_exam) C++14
39 / 100
 1000 ms 80448 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;
                } else break;
                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;
                } else break;
                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

# 결과 실행 시간 메모리 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 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
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 14 ms 612 KB Output is correct
3 Correct 47 ms 1624 KB Output is correct
4 Correct 25 ms 1868 KB Output is correct
5 Correct 93 ms 1780 KB Output is correct
6 Correct 35 ms 1764 KB Output is correct
7 Correct 41 ms 1868 KB Output is correct
8 Correct 72 ms 1772 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 15 ms 316 KB Output is correct
4 Correct 62 ms 556 KB Output is correct
5 Correct 67 ms 420 KB Output is correct
6 Correct 77 ms 408 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 80448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 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 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 1 ms 512 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

# 결과 실행 시간 메모리 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 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 212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 15 ms 316 KB Output is correct
10 Correct 62 ms 556 KB Output is correct
11 Correct 67 ms 420 KB Output is correct
12 Correct 77 ms 408 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Incorrect 1 ms 724 KB Output isn't correct
16 Halted 0 ms 0 KB -