oj.uz

Submission #833585

# Submission time Handle Problem Language Result Execution time Memory
833585 2023-08-22T07:00:05 Z vjudge1 Exam (eJOI20_exam) C++17
27 / 100
 304 ms 198460 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 71 ms 196384 KB Output is correct
2 Correct 69 ms 196304 KB Output is correct
3 Correct 66 ms 196300 KB Output is correct
4 Correct 68 ms 196404 KB Output is correct
5 Correct 66 ms 196296 KB Output is correct
6 Correct 304 ms 198460 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 196328 KB Output is correct
2 Incorrect 81 ms 196540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 196396 KB Output is correct
2 Correct 78 ms 196400 KB Output is correct
3 Correct 91 ms 196300 KB Output is correct
4 Correct 150 ms 196440 KB Output is correct
5 Correct 144 ms 196432 KB Output is correct
6 Correct 117 ms 196432 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 196384 KB Output is correct
2 Correct 69 ms 196304 KB Output is correct
3 Correct 66 ms 196300 KB Output is correct
4 Correct 68 ms 196404 KB Output is correct
5 Correct 66 ms 196296 KB Output is correct
6 Correct 304 ms 198460 KB Output is correct
7 Incorrect 82 ms 196400 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 196384 KB Output is correct
2 Correct 69 ms 196304 KB Output is correct
3 Correct 66 ms 196300 KB Output is correct
4 Correct 68 ms 196404 KB Output is correct
5 Correct 66 ms 196296 KB Output is correct
6 Correct 304 ms 198460 KB Output is correct
7 Correct 83 ms 196396 KB Output is correct
8 Correct 78 ms 196400 KB Output is correct
9 Correct 91 ms 196300 KB Output is correct
10 Correct 150 ms 196440 KB Output is correct
11 Correct 144 ms 196432 KB Output is correct
12 Correct 117 ms 196432 KB Output is correct
13 Incorrect 82 ms 196400 KB Output isn't correct
14 Halted 0 ms 0 KB -