5308 2023. 04. 25 18:59:15 gortomi Regex cpp17 Wrong answer 0/100 196ms 82696 KiB 
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<vector<int> > dp1(n + 1, vector<int>(m + 1)), dp2(n + 1, vector<int>(m + 1));
    for(int i = 0; i <= n; i++)
    {
        dp1[i][m] = n - i + 3;
        dp2[i][m] = n - i;
    }
    for(int i = 0; i <= m; i++)
    {
        dp1[n][i] = m - i + 3;
        dp2[n][i] = m - i;
    }
    dp1[n][m] = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = m - 1; j >= 0; j--)
        {
            if(a[i] == b[j])
            {
                dp1[i][j] = dp1[i + 1][j + 1] + 1;
                dp2[i][j] = dp1[i + 1][j + 1] + 1;
            }
            else dp1[i][j] = min(dp2[i + 1][j] + 4, dp2[i][j + 1] + 4);
            dp2[i][j] = min(dp2[i][j], dp2[i + 1][j] + 1);
            dp2[i][j] = min(dp2[i][j], dp2[i][j + 1] + 1);
        }
    }
    cout << dp1[0][0] << "\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1836 KiB
2 Wrong answer 3ms 2184 KiB
subtask2 0/9
3 Wrong answer 30ms 49968 KiB
4 Wrong answer 123ms 60624 KiB
5 Wrong answer 142ms 70844 KiB
6 Wrong answer 146ms 49136 KiB
7 Wrong answer 165ms 71408 KiB
8 Wrong answer 142ms 68384 KiB
subtask3 0/11
9 Wrong answer 3ms 3080 KiB
10 Wrong answer 3ms 3188 KiB
11 Wrong answer 3ms 3196 KiB
12 Wrong answer 3ms 3396 KiB
13 Wrong answer 3ms 3608 KiB
14 Wrong answer 3ms 3816 KiB
subtask4 0/13
15 Wrong answer 3ms 3952 KiB
16 Wrong answer 3ms 3968 KiB
17 Wrong answer 3ms 4008 KiB
18 Wrong answer 3ms 3992 KiB
19 Wrong answer 3ms 4188 KiB
20 Wrong answer 3ms 4180 KiB
subtask5 0/24
21 Wrong answer 3ms 4952 KiB
22 Wrong answer 4ms 5096 KiB
23 Wrong answer 4ms 5196 KiB
24 Wrong answer 4ms 5116 KiB
25 Wrong answer 3ms 5028 KiB
26 Wrong answer 4ms 5216 KiB
subtask6 0/43
27 Wrong answer 39ms 58368 KiB
28 Wrong answer 156ms 64708 KiB
29 Wrong answer 158ms 79964 KiB
30 Wrong answer 194ms 82696 KiB
31 Wrong answer 86ms 38140 KiB
32 Wrong answer 143ms 61408 KiB
33 Wrong answer 196ms 70240 KiB
34 Wrong answer 177ms 82104 KiB