Submission #833635

#	Time	Username	Problem	Language	Result	Execution time	Memory
833635		vjudge1	Exam (eJOI20_exam)	C++17	0 / 100	7 ms	6356 KiB

exam

#include <bits/stdc++.h>

using namespace std;

const int N = 5002;
int op[N][N];   //op[L][R] = number of (Hi == Ti) where (L ≤ i ≤ R) if we change H[L..R] to max(H[L..R])
int dp[N]; 
int n;
vector<int>h, t;

void solve24(){
    cout << "hehe" << endl;
}

int f(int i){
    if(i > n) return 0;
    int &cur = dp[i];

    if(cur != -1) return cur;

    cur = f(i + 1) + (h[i] == t[i]);    //skip i
    for(int j = i + 1; j <= n; j++){
        cur = max(cur, op[i][j] + f(j + 1));
    }

    return cur;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
    cin >> n;
    h.resize(n + 1);
    t.resize(n + 1);

    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> t[i];

    if(n > 5000){
        solve24();
        return 0;
    }   

    memset(dp, -1, sizeof(dp));

    for(int i = 1; i <= n; i++){
        map<int, int>freq;
        freq[t[i]]++;

        int maxi = h[i];
        for(int j = i + 1; j <= n; j++){
            freq[t[j]]++;
            maxi = max(maxi, h[j]);

            op[i][j] = freq[maxi];
        }
    }

    cout << f(1) << '\n';

    return 0;   
}

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