Submission #1130148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130148		cutimeo	Exam (eJOI20_exam)	C++20	13 / 100	649 ms	397704 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];
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 = 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], g[j] + ded[i][j]);
             //9   cout << f[i][j] << " " << i << " " << j << " " << mx[i - 1] << " " << val[2] << endl;
                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 = 0; j <= n; j ++){
                if (j <= i) cal[j] = 0;
                else{
                    cal[j] = max(cal[j], f[i][j]);
                }
                g[j] = cal[j] - max(0,d[sus[i][j]][j] - d[sus[i][j]][i]);
                if (j != 0) g[j] = max(g[j], g[j - 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: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22