제출 #1130205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130205		cutimeo	Exam (eJOI20_exam)	C++20	0 / 100	1117 ms	465912 KiB

exam

#include<bits/stdc++.h>
using namespace std;
int n;
int a[5005], b[5005];
int f[5005][5005];
int mx[5005];
int sl[10005];
int g[5005];
int d[10005][5005];
int sus[5005][5005];
int ded[5005][5005];
int val[5005];
int cal[5005];
int iuiem[10005][5005];
int h[10005];
int meo[10005];
namespace sub1{
    void solve(){
        mx[0] = 0;
        for (int i = 1; i <= n; i ++){
            for (int j = i;j <= n; j ++){
                if (j == i) sus[i][j] = a[j];
                else sus[i][j] = max(sus[i][j - 1], a[j]);
            }
        }
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= 2 * n; j ++) sl[j] = 0;
            for (int j = i; j <= n; j ++){
                sl[b[j]] ++;
                ded[i][j] = sl[sus[i][j]];
            }
        }
        for (int j = 1; j <= 2 * n; j ++){
            for (int i = 1; i <= n; i ++){
                d[j][i] = d[j][i - 1];
                if (b[i] == j) d[j][i] ++;
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i ++){
            for (int j = n; j >= 1; j --){
                iuiem[b[i]][j + 1] = iuiem[b[i]][j];

            }
            int lst = 0;
            for (int j = n; j >= 1; j --){
                if (iuiem[b[i]][j]){
                    lst = j;
                    break;
                }
            }
            h[b[i]] = lst;
            for (int j = 1; j <= 2 * n ; j ++){
                meo[j] = max(meo[j - 1], h[j]);
            }
            for (int j = i; j <= n; j ++){
                // f[u][k] =
                // case k < i
                f[i][j] = mx[i - 1] + ded[i][j];
                f[i][j] = max(f[i][j], meo[sus[i][j] - 1]);
                val[j] = max(val[j], f[i][j]);
                res = max(res, f[i][j]);
            }
            for (int j = 0; j <= n; j ++){
                if (a[i] == b[i] && i > j) val[j] ++;
                if (j == 0) mx[j] = val[j];
                else mx[j] =max(val[j], mx[j - 1]);

            }
            for (int j = 1; j <= i; j ++){
                iuiem[sus[j][i]][f[j][i] - (d[sus[j][i]][i] - d[sus[j][i]][i - 1])] --;
            }

        }
        cout << res << endl;
    }
};
namespace sub2{

};
namespace sub4{

};

int main(){
    cin >> n;
    map<int, int> hihi;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
        hihi[a[i]] = 1;
    }
    for (int i = 1; i <= n; i ++){
        cin >> b[i];
        hihi[b[i]] = 1;
    }
    int cnt = 1;
    for (auto i : hihi){
        hihi[i.first] = cnt;
        cnt ++;
    }
    for (int i = 1; i <= n; i ++ ){
        a[i] = hihi[a[i]];
        b[i] = hihi[b[i]];
    }
    sub1::solve();

}

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