Submission #833340

#	Time	Username	Problem	Language	Result	Execution time	Memory
833340		vjudge1	Exam (eJOI20_exam)	C++17	0 / 100	1095 ms	41932 KiB

exam

#include <bits/stdc++.h>
using namespace std;

int n;
int h[100005];
int t[100005];
int dp[5005][5005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    for (int i = 0; i < n; i++) {
        dp[i][i] = (h[i] == t[i] ? 1 : 0);
    }
    for (int d = 1; d < n; d++) {
        for (int i = 0; i + d < n; i++) {
            dp[i][i+d] = 0;
            for (int j = i; j < i + d; j++) {
                dp[i][i+d] = max(dp[i][i+d], dp[i][j] + dp[j+1][i+d]);
            }
            int maxx = 0;
            for (int j = i; j <= i + d; j++) {
                maxx = max(maxx, h[j]);
            }
            int cnt = 0;
            for (int j = i; j <= i + d; j++) {
                if (t[j] == maxx) {
                    cnt++;
                }
            }
            dp[i][i+d] = max(dp[i][i+d], cnt);
        }
    }
    cout << dp[0][n-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