oj.uz

Submission #466697

# Submission time Handle Problem Language Result Execution time Memory
466697 2021-08-20T09:16:47 Z Valaki2 Exam (eJOI20_exam) C++14
39 / 100
 61 ms 2508 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;
vector<int> b;

void solve_bf() {
    set<int> a_set;
    vector<bool> possible(1 + n, false);
    for(int i = 1; i <= n; ++i) a_set.insert(a[i]);
    for(int i = 1; i <= n; ++i) if(a_set.count(b[i])) possible[i] = true;
    int ans = 0;
    vector<bool> cur(1 + n, false);
    for(int mask = 0; mask < (1 << n); ++mask) {
        bool ok = true;
        for(int i = 0; i < n; ++i) {
            if(mask & (1 << i)) {
                cur[i + 1] = true;
                if(!possible[i + 1]) ok = false;
            } else {
                cur[i + 1] = false;
            }
        }
        if(!ok) continue;
        for(int i = 1; i <= n; ++i) {
            if(!cur[i]) continue;
            bool done = false;
            for(int j = i; j >= 1; --j) {
                if(a[j] > b[i] || (cur[j] && b[j] < b[i])) break;
                if(a[j] == b[i]) {
                    done = true;
                    break;
                }
            }
            for(int j = i; j <= n; ++j) {
                if(a[j] > b[i] || (cur[j] && b[j] < b[i])) break;
                if(a[j] == b[i]) {
                    done = true;
                    break;
                }
            }
            if(!done) ok = false;
        }
        if(ok) ans = max(ans, __builtin_popcount(mask));
    }
    cout << ans << "\n";
}

void solve_bequal() {
    int x = b[1];
    int last = 0;
    bool ok = false;
    int ans = 0;
    a.push_back(x + 1);
    for(int i = 1; i <= (n + 1); ++i) {
        if(a[i] > x) {
            if(ok) {
                ans += i - last - 1;
                ok = false;
            }
            last = i;
        } else if(a[i] == x) {
            ok = true;
        }
    }
    cout << ans << "\n";
}

void solve_astrictlyincreasing() {
    vector<int> dp(1 + n, 0);
    for(int i = 1; i <= n; ++i) {
        vector<int> cnt_left(1 + i + 1, 0);
        // vector<int> cnt_right(1 + i + 1, 0);
        for(int j = 1; j <= i; ++j) {
            cnt_left[j] = cnt_left[j - 1];
            if(b[j] == a[i]) ++cnt_left[j];
        }
        /*for(int j = i; j >= 1; --j) {
            cnt_right[j] = cnt_right[j + 1];
            if(b[j] == a[i]) ++cnt_right[j];
        }*/
        int maxi = 0;
        for(int j = 1; j <= i; ++j) {
            maxi = max(maxi, dp[j] - cnt_left[j]);
            dp[j] = max(dp[j], maxi + cnt_left[j]);
        }
    }
    cout << dp[n] << "\n";
}

void solve() {
    cin >> n;
    a.assign(1 + n, 0);
    b.assign(1 + n, 0);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    set<int> b_set;
    for(int i = 1; i <= n; ++i) {
        b_set.insert(b[i]);
    }
    if(n <= 10) {
        solve_bf();
    } else if(b_set.size() == 1) {
        solve_bequal();
    } else {
        solve_astrictlyincreasing();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 8 ms 844 KB Output is correct
3 Correct 19 ms 2372 KB Output is correct
4 Correct 16 ms 1864 KB Output is correct
5 Correct 29 ms 2508 KB Output is correct
6 Correct 18 ms 1752 KB Output is correct
7 Correct 17 ms 1976 KB Output is correct
8 Correct 27 ms 2432 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 10 ms 460 KB Output is correct
4 Correct 61 ms 460 KB Output is correct
5 Correct 59 ms 588 KB Output is correct
6 Correct 58 ms 588 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 10 ms 460 KB Output is correct
10 Correct 61 ms 460 KB Output is correct
11 Correct 59 ms 588 KB Output is correct
12 Correct 58 ms 588 KB Output is correct
13 Incorrect 1 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -