답안 #1104014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104014	2024-10-22T14:57:25 Z	manhlinh1501	Exam (eJOI20_exam)	C++17	25 / 100	70 ms	76444 KB

exam

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 2e5 + 5;
#define left ___left
#define right ___right
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);
    }
}

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();
//    for(int i = 1; i <= N; i++) cout << a[i] << " ";
//    cout << "\n";
//    for(int i = 1; i <= N; i++) cout << b[i] << " ";
//    cout << "\n";
    subtask2::solution();
    subtask3::solution();
    return (0 ^ 0);
}

Compilation message

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

Subtask #1
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	2384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4432 KB	Output is correct
2	Correct	5 ms	4432 KB	Output is correct
3	Correct	31 ms	9040 KB	Output is correct
4	Correct	12 ms	4944 KB	Output is correct
5	Correct	70 ms	9544 KB	Output is correct
6	Correct	11 ms	4944 KB	Output is correct
7	Correct	16 ms	5032 KB	Output is correct
8	Correct	60 ms	7752 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2384 KB	Output is correct
2	Correct	3 ms	5112 KB	Output is correct
3	Correct	17 ms	22540 KB	Output is correct
4	Correct	50 ms	72188 KB	Output is correct
5	Correct	49 ms	76444 KB	Output is correct
6	Correct	49 ms	76360 KB	Output is correct