167272025-05-11 15:41:29TaxiradioRegexcpp17Wrong answer 0/100226ms39552 KiB
// Source: https://usaco.guide/general/io

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

const int lim = 2000000000;

int main() {
	int t;cin >> t; 
    while(t--){
        string a , b; cin >> a >> b;
        int n = a.size() , m = b.size();
        vector<vector<int>> dp1(n+2 , vector<int>(m+2 , lim)) , dp2(n+2 , vector<int>(m+2 , lim));
        dp1[1][1] = 0;
        dp2[1][1] = 3;
        for(int i = 1; i < n+2; i++){
            for(int j = 1; j < m+2; j++){
                dp2[i][j] = min(min(min(dp1[i-1][j]+4 , dp1[i][j-1]+4) , min(dp2[i-1][j]+1 , dp2[i][j-1]+1)), dp2[i][j]);
                if(i != 1 && j!=1 && a[i-2] == b[i-2]){
                    dp1[i][j] = min(dp1[i-1][j-1]+1 , dp1[i][j]);
                }else{
                    dp1[i][j] = min(dp2[i][j] , dp1[i][j]);
                }
            }
        }
        cout << dp1.back().back() << "\n";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Wrong answer1ms316 KiB
subtask20/9
3Wrong answer39ms24372 KiB
4Wrong answer170ms29676 KiB
5Wrong answer152ms34612 KiB
6Wrong answer152ms23588 KiB
7Wrong answer226ms34664 KiB
8Wrong answer170ms33236 KiB
subtask30/11
9Accepted1ms508 KiB
10Wrong answer1ms508 KiB
11Wrong answer1ms316 KiB
12Accepted1ms564 KiB
13Wrong answer1ms316 KiB
14Wrong answer1ms316 KiB
subtask40/13
15Wrong answer1ms316 KiB
16Wrong answer1ms316 KiB
17Wrong answer1ms316 KiB
18Wrong answer1ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
subtask50/24
21Wrong answer2ms564 KiB
22Wrong answer2ms820 KiB
23Wrong answer2ms756 KiB
24Wrong answer2ms564 KiB
25Wrong answer2ms648 KiB
26Wrong answer2ms684 KiB
subtask60/43
27Wrong answer43ms27188 KiB
28Wrong answer156ms30596 KiB
29Wrong answer162ms38316 KiB
30Wrong answer216ms39552 KiB
31Wrong answer111ms17204 KiB
32Wrong answer125ms28724 KiB
33Wrong answer193ms33076 KiB
34Wrong answer193ms39220 KiB