oj.uz

답안 #833576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833576 2023-08-22T06:58:04 Z vjudge1 Exam (eJOI20_exam) C++17
14 / 100
 284 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 = 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 = 1; i <= N; i++) {
                  if(H[i] > T[1]) continue;
                  int j = i;
                  bool hv = H[i] == T[1];
                  while(j + 1 <= N && H[j + 1] <= T[1]) {
                        j++;
                        hv |= H[j] == T[1];
                  }

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

            for(int i = N; i >= 1; 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; j >= 1; j--) {
                        mx[i][j] = max(dp[i][j], mx[i][j + 1]);
                  }
            }

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

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 196368 KB Output is correct
2 Correct 78 ms 196360 KB Output is correct
3 Correct 71 ms 196280 KB Output is correct
4 Correct 81 ms 196496 KB Output is correct
5 Correct 78 ms 196328 KB Output is correct
6 Correct 284 ms 198492 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 196408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 196276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 188 ms 196432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 196368 KB Output is correct
2 Correct 78 ms 196360 KB Output is correct
3 Correct 71 ms 196280 KB Output is correct
4 Correct 81 ms 196496 KB Output is correct
5 Correct 78 ms 196328 KB Output is correct
6 Correct 284 ms 198492 KB Output is correct
7 Incorrect 85 ms 196300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 196368 KB Output is correct
2 Correct 78 ms 196360 KB Output is correct
3 Correct 71 ms 196280 KB Output is correct
4 Correct 81 ms 196496 KB Output is correct
5 Correct 78 ms 196328 KB Output is correct
6 Correct 284 ms 198492 KB Output is correct
7 Incorrect 87 ms 196276 KB Output isn't correct
8 Halted 0 ms 0 KB -