제출 #1127374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127374		khanhphucscratch	Exam (eJOI20_exam)	C++20	0 / 100	33 ms	580 KiB

exam

//n <= 5000, subtask 1, 3, 5, 6
#include<bits/stdc++.h>
using namespace std;
int dp[5005], a[5005], b[5005], f[10005], best[10005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) cin>>b[i];
    vector<int> vec1, vec2;
    for(int i = 1; i <= n; i++) vec1.push_back(a[i]);
    for(int i = 1; i <= n; i++) vec1.push_back(b[i]);
    sort(vec1.begin(), vec1.end());
    for(int i = 0; i < vec1.size(); i++) if(i == 0 || vec1[i] != vec1[i-1]) vec2.push_back(vec1[i]);
    for(int i = 1; i <= n; i++) a[i] = upper_bound(vec2.begin(), vec2.end(), a[i]) - vec2.begin();
    for(int i = 1; i <= n; i++) b[i] = upper_bound(vec2.begin(), vec2.end(), b[i]) - vec2.begin();
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i-1];
        int curmax = 0;
        memset(f, 0, sizeof(f));
        memset(best, 0, sizeof(best));
        for(int j = i; j >= 1; j--){
            f[b[j]]++; best[b[j]] = max(best[b[j]], f[b[j]] + dp[j-1]);
            curmax = max(curmax, a[j]);
            dp[i] = max(dp[i], best[curmax]);
        }
    }
    cout<<dp[n];
}

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