Submission #18760756

Source Code Expand

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

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

  ll N; cin >> N;
  ll M; cin >> M;
  vector<ll> A(N); for (ll i = 0; i < N; i++) cin >> A[i];
  vector<ll> B(M); for (ll i = 0; i < M; i++) cin >> B[i];

  vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 1e15));
  for (ll i = 0; i < N + 1; i++) {
    dp[i][0] = i;
  }
  for (ll i = 0; i < M + 1; i++) {
    dp[0][i] = i;
  }
  for (ll i = 1; i <= N; i++) {
    for (ll j = 1; j <= M; j++) {
      ll m = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
      if (A[i - 1] == B[j - 1]) {
        dp[i][j] = min(m, dp[i - 1][j - 1]);
      } else {
        dp[i][j] = min(m, dp[i - 1][j - 1] + 1);
      }
    }
  }
  ll ans = dp[N][M];
  cout << ans << '\n';
  return 0;
}

Submission Info

Submission Time
Task E - Sequence Matching
User nakaken88
Language C++ (GCC 9.2.1)
Score 500
Code Size 825 Byte
Status AC
Exec Time 17 ms
Memory 11108 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All extreme_00.txt, extreme_01.txt, extreme_02.txt, extreme_03.txt, extreme_04.txt, extreme_05.txt, extreme_06.txt, handmade_00.txt, handmade_01.txt, pattern_00.txt, pattern_01.txt, pattern_02.txt, pattern_03.txt, pattern_04.txt, pattern_05.txt, pattern_06.txt, pattern_07.txt, pattern_08.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
extreme_00.txt AC 14 ms 11108 KiB
extreme_01.txt AC 14 ms 11040 KiB
extreme_02.txt AC 14 ms 11020 KiB
extreme_03.txt AC 17 ms 10964 KiB
extreme_04.txt AC 15 ms 10960 KiB
extreme_05.txt AC 3 ms 3556 KiB
extreme_06.txt AC 2 ms 3644 KiB
handmade_00.txt AC 3 ms 3524 KiB
handmade_01.txt AC 2 ms 3472 KiB
pattern_00.txt AC 14 ms 11044 KiB
pattern_01.txt AC 13 ms 10976 KiB
pattern_02.txt AC 13 ms 11048 KiB
pattern_03.txt AC 7 ms 4680 KiB
pattern_04.txt AC 5 ms 3652 KiB
pattern_05.txt AC 4 ms 3652 KiB
pattern_06.txt AC 6 ms 5500 KiB
pattern_07.txt AC 4 ms 4164 KiB
pattern_08.txt AC 4 ms 4976 KiB
random_00.txt AC 17 ms 11044 KiB
random_01.txt AC 14 ms 11104 KiB
random_02.txt AC 15 ms 11044 KiB
random_03.txt AC 4 ms 3576 KiB
random_04.txt AC 2 ms 3460 KiB
random_05.txt AC 4 ms 3648 KiB
random_06.txt AC 7 ms 5504 KiB
random_07.txt AC 6 ms 4124 KiB
random_08.txt AC 5 ms 4972 KiB
random_09.txt AC 13 ms 6796 KiB
sample_01.txt AC 3 ms 3504 KiB
sample_02.txt AC 2 ms 3568 KiB
sample_03.txt AC 5 ms 3520 KiB