oj.uz

Submission #833635

# Submission time Handle Problem Language Result Execution time Memory
833635 2023-08-22T07:17:36 Z vjudge1 Exam (eJOI20_exam) C++17
0 / 100
 7 ms 6356 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6356 KB Output is correct
2 Incorrect 4 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -