Submission #833588

#	Time	Username	Problem	Language	Result	Execution time	Memory
833588		vjudge1	Exam (eJOI20_exam)	C++17	39 / 100	266 ms	198492 KiB

exam

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

const int MX = 1e5 + 5;

int N;
int H[MX], T[MX];
map<vector<int>, int> memo;

int f(vector<int> v) {
      if(memo.count(v)) return memo[v];

      int res = 0;

      for(int i = 0; i < N; i++) res += v[i] == T[i];

      for(int l = 0; l < N; l++) {
            int mx = 0;
            for(int r = l; r < N; r++) {
                  mx = max(mx, v[r]);

                  vector<int> nv = v;

                  for(int k = l; k <= r; k++) nv[k] = mx;

                  if(nv != v)
                        res = max(res, f(nv));
            }
      }

      return memo[v] = res;
}

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

      cin >> N;

      for(int i = 0; i < N; i++) cin >> H[i];
      for(int i = 0; i < N; i++) cin >> T[i];

      bool same = 1;
      for(int i = 0; i < N; i++) same &= T[0] == T[i];
      
      if(N <= 10) {
            vector<int> v;
            for(int i = 0; i < N; i++) v.push_back(H[i]);

            cout << f(v) << '\n';
      } else if(same) {
            int ans = 0;
            for(int i = 0; i < N; i++) {
                  if(H[i] > T[0]) continue;
                  int j = i;
                  bool hv = H[i] == T[0];
                  while(j + 1 < N && H[j + 1] <= T[0]) {
                        j++;
                        hv |= H[j] == T[0];
                  }

                  if(hv) {
                        ans += j - i + 1;
                        i = j;
                  }
            }
            cout << ans << '\n';
      } else {
            int dp[5005][5005] = {};
            int mx[5005][5005] = {};

            for(int i = N - 1; i >= 0; i--) {
                  for(int j = i; j < N; j++) {
                        dp[i][j] = max(dp[i][j], mx[i + 1][j] + (T[i] == H[j]));
                  }
                  for(int j = N - 1; j >= 0; j--) {
                        mx[i][j] = max(dp[i][j], mx[i][j + 1]);
                  }
            }

            cout << mx[0][0] << '\n';
      }
}

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