oj.uz

Submission #1104213

# Submission time Handle Problem Language Result Execution time Memory
1104213 2024-10-23T09:02:12 Z manhlinh1501 Exam (eJOI20_exam) C++17
77 / 100
 74 ms 101436 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 2e5 + 5;
#define left ___left
#define right ___right
#define ALL(a) (a).begin(), (a).end()

using pii = pair<int, int>;
int N;
int a[MAXN];
int b[MAXN];

void compress() {
    map<int, int> comp;
    for(int i = 1; i <= N; i++) comp[a[i]] = 1;
    for(int i = 1; i <= N; i++) comp[b[i]] = 1;
    int c = 0;
    for(auto &[x, y] : comp) y = ++c;
    for(int i = 1; i <= N; i++) a[i] = comp[a[i]];
    for(int i = 1; i <= N; i++) b[i] = comp[b[i]];
}

namespace subtask2 {
    bool is_subtask() {
        for(int i = 1; i < N; i++) {
            if(b[i] != b[i + 1]) return false;
        }
        return true;
    }
    int left[MAXN];
    int right[MAXN];
    int cnt[MAXN];

    void solution() {
        if(is_subtask() == false) return;
        for(int i = 1; i <= N; i++) {
            left[i] = i - 1;
            while(left[i] > 0 and a[left[i]] <= a[i])
                left[i] = left[left[i]];
        }
        for(int i = N; i >= 1; i--) {
            right[i] = i + 1;
            while(right[i] <= N and a[right[i]] <= a[i])
                right[i] = right[right[i]];
        }
        for(int i = 1; i <= N; i++) {
            left[i]++;
            right[i]--;
        }
        for(int i = 1; i <= N; i++) {
            if(a[i] == b[i]) {
                cnt[left[i]]++;
                cnt[right[i] + 1]--;
            }
        }
        for(int i = 1; i <= N; i++) cnt[i] += cnt[i - 1];
        int ans = 0;
        for(int i = 1; i <= N; i++) ans += (cnt[i] > 0);
        cout << ans;
        exit(0);
    }
}

namespace subtask3 {
    const int MAXN = 5e3 + 5;
    bool is_subtask() {
        return is_sorted(a + 1, a + N + 1);
    }
    int dp[MAXN][MAXN];

    void solution() {
        if(is_subtask() == false) return;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if(a[i] == b[j])
                    dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], dp[i][j - 1]) + 1);
            }
        }
        int ans = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= i; j++)
                ans = max(ans, dp[i][j]);
        }
        cout << ans;
        exit(0);
    }
}

namespace subtask4 {
    const int LOGN = 20;
    bool is_subtask() {
        vector<int> b;
        for(int i = 1; i <= N; i++) b.emplace_back(a[i]);
        sort(ALL(b));
        for(int i = 1; i < N; i++) {
            if(b[i] == b[i - 1]) return false;
        }
        return true;
    }

    void solution() {
        if(is_subtask() == false) return;
        exit(0);
    }
}

namespace subtask6 {
    const int MAXN = 5e3 + 5;

    int dp[MAXN][MAXN];
    int left[MAXN];
    int right[MAXN];

    bool is_subtask() {
        return N < MAXN;
    }

    void solution() {
        if(is_subtask() == false) return;
        for(int i = 1; i <= N; i++) {
            left[i] = i - 1;
            while(left[i] > 0 and a[left[i]] <= a[i])
                left[i] = left[left[i]];
        }
        for(int i = N; i >= 1; i--) {
            right[i] = i + 1;
            while(right[i] <= N and a[right[i]] <= a[i])
                right[i] = right[right[i]];
        }
        for(int i = 1; i <= N; i++) {
            left[i]++;
            right[i]--;
        }
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if(a[i] == b[j] and left[i] <= j and j <= right[i])
                    dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1);
            }
        }
        int ans = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++)
                ans = max(ans, dp[i][j]);
        }
        cout << ans;
        exit(0);
    }
}

signed main() {
#define task "code"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int i = 1; i <= N; i++) cin >> b[i];
    compress();
    subtask2::solution();
    subtask3::solution();
//    subtask4::solution();
    subtask6::solution();
    return (0 ^ 0);
}

Compilation message

exam.cpp: In function 'int main()':
exam.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
exam.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 5 ms 4432 KB Output is correct
3 Correct 32 ms 9148 KB Output is correct
4 Correct 10 ms 4944 KB Output is correct
5 Correct 74 ms 9544 KB Output is correct
6 Correct 13 ms 4944 KB Output is correct
7 Correct 17 ms 4944 KB Output is correct
8 Correct 65 ms 7752 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 16 ms 21840 KB Output is correct
4 Correct 53 ms 73784 KB Output is correct
5 Correct 55 ms 77896 KB Output is correct
6 Correct 55 ms 77896 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 101200 KB Output is correct
2 Incorrect 38 ms 5212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2520 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 2 ms 2896 KB Output is correct
10 Correct 2 ms 3408 KB Output is correct
11 Correct 2 ms 3408 KB Output is correct
12 Correct 2 ms 3408 KB Output is correct
13 Correct 2 ms 3408 KB Output is correct
14 Correct 2 ms 3408 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2480 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2520 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 3 ms 4944 KB Output is correct
9 Correct 16 ms 21840 KB Output is correct
10 Correct 53 ms 73784 KB Output is correct
11 Correct 55 ms 77896 KB Output is correct
12 Correct 55 ms 77896 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 1 ms 2640 KB Output is correct
15 Correct 2 ms 2896 KB Output is correct
16 Correct 2 ms 3408 KB Output is correct
17 Correct 2 ms 3408 KB Output is correct
18 Correct 2 ms 3408 KB Output is correct
19 Correct 2 ms 3408 KB Output is correct
20 Correct 2 ms 3408 KB Output is correct
21 Correct 2 ms 3408 KB Output is correct
22 Correct 9 ms 10320 KB Output is correct
23 Correct 3 ms 4856 KB Output is correct
24 Correct 62 ms 101236 KB Output is correct
25 Correct 60 ms 101196 KB Output is correct
26 Correct 53 ms 101192 KB Output is correct
27 Correct 60 ms 101192 KB Output is correct
28 Correct 53 ms 101436 KB Output is correct
29 Correct 49 ms 77884 KB Output is correct
30 Correct 62 ms 100680 KB Output is correct
31 Correct 69 ms 100680 KB Output is correct
32 Correct 64 ms 100668 KB Output is correct