제출 #383005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383005		valerikk	Exam (eJOI20_exam)	C++17	77 / 100	240 ms	122860 KiB

exam

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
const int M = 1e5 + 7;

int n;
int a[M], b[M];
bool ok[N][N];
int dp[N][N];

void solve_b_equal() {
    int B = b[0];
    vector<int> inds;
    inds.push_back(-1);
    for (int i = 0; i < n; ++i) {
        if (a[i] > B) inds.push_back(i); 
    }
    inds.push_back(n);
    int ans = 0;
    for (int i = 0; i + 1 < inds.size(); ++i) {
        bool ok = false;
        for (int j = inds[i] + 1; j < inds[i + 1]; ++j) {
            ok |= a[j] == B;
        }
        if (ok) ans += inds[i + 1] - inds[i] - 1;
    }
    cout << ans << endl;
}

void solve_a_distinct() {

}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    
    bool b_equal = true;
    for (int i = 1; i < n; ++i) b_equal &= b[i] == b[i - 1];
    if (b_equal) {
        solve_b_equal();
        return 0;
    } 
    
    /*vector<int> A;
    for (int i = 0; i < n; ++i) A.push_back(a[i]);
    sort(A.begin(), A.end());
    bool a_distinct = true;
    for (int i = 1; i < n; ++i) a_distinct &= A[i] != A[i - 1];
    if (a_distinct) {
        solve_a_distinct();
    }*/
    
    for (int i = 0; i < n; ++i) {
        ok[i][i] = true;
        for (int j = i - 1; j >= 0; --j) {
            if (a[j] > a[i]) break;
            ok[j][i] = true;
        }
        for (int j = i + 1; j < n; ++j) {
            if (a[j] > a[i]) break;
            ok[j][i] = true;
        }
    }
    
    for (int i = 0; i < n; ++i) {
        if (ok[0][i] && b[0] == a[i]) {
            dp[0][i] = 1;
        }
    }
    for (int i = 1; i < n; ++i) {
        int mx = 0;
        for (int j = 0; j < n; ++j) {
            mx = max(mx, dp[i - 1][j]);
            if (ok[i][j]) {
                dp[i][j] = mx;
                if (b[i] == a[j]) ++dp[i][j];
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; ++i) ans = max(ans, dp[n - 1][i]);
    cout << ans << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

exam.cpp: In function 'void solve_b_equal()':
exam.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i + 1 < inds.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22