5374 2023. 04. 26 19:48:04 rmlan Regex cpp14 Wrong answer 24/100 104ms 83072 KiB 
#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        string a,b;
        cin >> a >> b;
        if(a.length() < b.length()) swap(a,b);
        int dp[a.length()+1][b.length()+1][2];
        dp[0][0][0]=0;
        dp[0][0][1]=3;
        for(int i = 1; i <= a.length(); i++){dp[i][0][1]=i+3; dp[i][0][0]=1e5;}
        for(int i = 1; i <= b.length(); i++){dp[0][i][1]=i+3; dp[0][i][0]=1e5;}
        for(int i = 1; i <= a.length(); i++){
            for(int j = 1; j <= b.length(); j++){
                if(a[i-1]==b[j-1]){
                    //cout << "ok";
                    dp[i][j][0]=min(dp[i-1][j-1][0], dp[i-1][j-1][1])+1;
                    dp[i][j][1]=dp[i-1][j-1][1]+2;
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][1]+1);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][1]+1);
                }else{

                    dp[i][j][0]=1e5;
                    dp[i][j][1]=dp[i-1][j-1][1]+2;
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][0]+5);
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][0]+4);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][0]+4);
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][1]+1);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][1]+1);
                }
            //cout << dp[i][j][0] << " "<<dp[i][j][1] << "    :" << i << " " << j << endl;
            }//cout << endl;
        }
        cout << min(dp[a.length()][b.length()][0], dp[a.length()][b.length()][1]) << endl;
    }
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1816 KiB
2 Accepted 3ms 2080 KiB
subtask2 0/9
3 Accepted 28ms 50256 KiB
4 Accepted 78ms 60592 KiB
5 Wrong answer 82ms 70920 KiB
6 Wrong answer 70ms 49376 KiB
7 Accepted 97ms 71400 KiB
8 Accepted 87ms 68468 KiB
subtask3 11/11
9 Accepted 3ms 3204 KiB
10 Accepted 2ms 3296 KiB
11 Accepted 3ms 3280 KiB
12 Accepted 2ms 3252 KiB
13 Accepted 3ms 3384 KiB
14 Accepted 3ms 3592 KiB
subtask4 13/13
15 Accepted 3ms 3720 KiB
16 Accepted 3ms 3984 KiB
17 Accepted 3ms 4204 KiB
18 Accepted 3ms 4520 KiB
19 Accepted 3ms 4468 KiB
20 Accepted 3ms 4372 KiB
subtask5 0/24
21 Accepted 3ms 5132 KiB
22 Accepted 4ms 5272 KiB
23 Accepted 3ms 5152 KiB
24 Wrong answer 4ms 5084 KiB
25 Accepted 3ms 5064 KiB
26 Accepted 4ms 5632 KiB
subtask6 0/43
27 Accepted 34ms 58408 KiB
28 Wrong answer 82ms 65012 KiB
29 Wrong answer 89ms 80328 KiB
30 Accepted 101ms 83072 KiB
31 Wrong answer 54ms 38568 KiB
32 Wrong answer 82ms 61620 KiB
33 Accepted 100ms 70288 KiB
34 Wrong answer 104ms 82224 KiB