oj.uz

Submission #833582

# Submission time Handle Problem Language Result Execution time Memory
833582 2023-08-22T06:59:23 Z vjudge1 Exam (eJOI20_exam) C++17
27 / 100
 267 ms 198480 KB 
#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 = 1; i <= N; i++) same &= T[1] == 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 69 ms 196296 KB Output is correct
3 Correct 68 ms 196404 KB Output is correct
4 Correct 67 ms 196324 KB Output is correct
5 Correct 90 ms 196300 KB Output is correct
6 Correct 267 ms 198480 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 196408 KB Output is correct
2 Correct 82 ms 196372 KB Output is correct
3 Correct 89 ms 196444 KB Output is correct
4 Correct 122 ms 196480 KB Output is correct
5 Correct 134 ms 196476 KB Output is correct
6 Correct 160 ms 196460 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 69 ms 196296 KB Output is correct
3 Correct 68 ms 196404 KB Output is correct
4 Correct 67 ms 196324 KB Output is correct
5 Correct 90 ms 196300 KB Output is correct
6 Correct 267 ms 198480 KB Output is correct
7 Incorrect 84 ms 196340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 69 ms 196296 KB Output is correct
3 Correct 68 ms 196404 KB Output is correct
4 Correct 67 ms 196324 KB Output is correct
5 Correct 90 ms 196300 KB Output is correct
6 Correct 267 ms 198480 KB Output is correct
7 Correct 81 ms 196408 KB Output is correct
8 Correct 82 ms 196372 KB Output is correct
9 Correct 89 ms 196444 KB Output is correct
10 Correct 122 ms 196480 KB Output is correct
11 Correct 134 ms 196476 KB Output is correct
12 Correct 160 ms 196460 KB Output is correct
13 Incorrect 84 ms 196340 KB Output isn't correct
14 Halted 0 ms 0 KB -