4054 2023. 03. 11 10:55:43 zsombor Regex cpp17 Accepted 100/100 122ms 145976 KiB 
#include <iostream>
#include <vector>
using namespace std;

string a, b;
int n, m;
vector <vector <int>> dp(3e3, vector <int>(3e3, 1e9));
vector <vector <int>> mn(3e3, vector <int>(3e3, 0));

void solve() {
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = "a" + a;
    b = "a" + b;
    dp[0][0] = n + m + 3;
    for (int i = 0; i <= n; i++) mn[i][0] = dp[0][0];
    for (int j = 0; j <= m; j++) mn[0][j] = dp[0][0];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]);
            if (a[i] != b[j]) continue;
            dp[i][j] = mn[i - 1][j - 1] + 2;
            if (a[i - 1] == b[j - 1]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] - 1);
            if (i == n && j == m) dp[i][j] -= 3;
            mn[i][j] = min(mn[i][j], dp[i][j]);
        }
    }
    cout << mn[n][m] << endl;
}

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) solve();
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 50ms 142892 KiB
2 Accepted 48ms 143052 KiB
subtask2 9/9
3 Accepted 71ms 143404 KiB
4 Accepted 90ms 143740 KiB
5 Accepted 104ms 143876 KiB
6 Accepted 92ms 143928 KiB
7 Accepted 104ms 144248 KiB
8 Accepted 111ms 144456 KiB
subtask3 11/11
9 Accepted 50ms 144404 KiB
10 Accepted 48ms 144420 KiB
11 Accepted 61ms 144532 KiB
12 Accepted 61ms 144548 KiB
13 Accepted 61ms 144800 KiB
14 Accepted 61ms 144876 KiB
subtask4 13/13
15 Accepted 50ms 144956 KiB
16 Accepted 48ms 144876 KiB
17 Accepted 61ms 144776 KiB
18 Accepted 48ms 144780 KiB
19 Accepted 61ms 145108 KiB
20 Accepted 63ms 145172 KiB
subtask5 24/24
21 Accepted 63ms 145052 KiB
22 Accepted 63ms 145260 KiB
23 Accepted 63ms 145264 KiB
24 Accepted 63ms 145348 KiB
25 Accepted 63ms 145484 KiB
26 Accepted 63ms 145412 KiB
subtask6 43/43
27 Accepted 61ms 145668 KiB
28 Accepted 112ms 145660 KiB
29 Accepted 111ms 145652 KiB
30 Accepted 119ms 145636 KiB
31 Accepted 79ms 145828 KiB
32 Accepted 104ms 145976 KiB
33 Accepted 122ms 145836 KiB
34 Accepted 103ms 145836 KiB