oj.uz

Submission #833588

# Submission time Handle Problem Language Result Execution time Memory
833588 2023-08-22T07:01:04 Z vjudge1 Exam (eJOI20_exam) C++17
39 / 100
 266 ms 198492 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 = 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 196300 KB Output is correct
2 Correct 66 ms 196272 KB Output is correct
3 Correct 67 ms 196388 KB Output is correct
4 Correct 67 ms 196332 KB Output is correct
5 Correct 68 ms 196404 KB Output is correct
6 Correct 266 ms 198492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 196288 KB Output is correct
2 Correct 86 ms 196504 KB Output is correct
3 Correct 76 ms 197008 KB Output is correct
4 Correct 75 ms 197064 KB Output is correct
5 Correct 83 ms 197136 KB Output is correct
6 Correct 101 ms 197068 KB Output is correct
7 Correct 77 ms 197104 KB Output is correct
8 Correct 82 ms 197172 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196396 KB Output is correct
2 Correct 87 ms 196408 KB Output is correct
3 Correct 92 ms 196356 KB Output is correct
4 Correct 154 ms 196428 KB Output is correct
5 Correct 124 ms 196384 KB Output is correct
6 Correct 158 ms 196376 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 196300 KB Output is correct
2 Correct 66 ms 196272 KB Output is correct
3 Correct 67 ms 196388 KB Output is correct
4 Correct 67 ms 196332 KB Output is correct
5 Correct 68 ms 196404 KB Output is correct
6 Correct 266 ms 198492 KB Output is correct
7 Incorrect 85 ms 196364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 196300 KB Output is correct
2 Correct 66 ms 196272 KB Output is correct
3 Correct 67 ms 196388 KB Output is correct
4 Correct 67 ms 196332 KB Output is correct
5 Correct 68 ms 196404 KB Output is correct
6 Correct 266 ms 198492 KB Output is correct
7 Correct 84 ms 196396 KB Output is correct
8 Correct 87 ms 196408 KB Output is correct
9 Correct 92 ms 196356 KB Output is correct
10 Correct 154 ms 196428 KB Output is correct
11 Correct 124 ms 196384 KB Output is correct
12 Correct 158 ms 196376 KB Output is correct
13 Incorrect 85 ms 196364 KB Output isn't correct
14 Halted 0 ms 0 KB -