167282025-05-11 15:45:41TaxiradioRegexcpp17Wrong answer 0/100266ms39676 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]);
                dp1[i][j] = min(dp2[i][j] , dp1[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]);
                }
            }
        }
        cout << dp1.back().back() << "\n";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Wrong answer1ms316 KiB
subtask20/9
3Wrong answer46ms24380 KiB
4Wrong answer182ms29504 KiB
5Wrong answer182ms34452 KiB
6Wrong answer201ms23576 KiB
7Wrong answer266ms34660 KiB
8Wrong answer204ms33240 KiB
subtask30/11
9Accepted1ms500 KiB
10Wrong answer1ms316 KiB
11Wrong answer1ms316 KiB
12Accepted1ms316 KiB
13Wrong answer1ms316 KiB
14Wrong answer1ms316 KiB
subtask40/13
15Wrong answer1ms508 KiB
16Wrong answer1ms316 KiB
17Wrong answer1ms500 KiB
18Wrong answer1ms508 KiB
19Wrong answer1ms316 KiB
20Wrong answer1ms316 KiB
subtask50/24
21Wrong answer2ms564 KiB
22Wrong answer3ms820 KiB
23Wrong answer2ms756 KiB
24Wrong answer2ms568 KiB
25Wrong answer2ms564 KiB
26Wrong answer3ms820 KiB
subtask60/43
27Wrong answer50ms27188 KiB
28Wrong answer190ms30564 KiB
29Wrong answer217ms38192 KiB
30Wrong answer232ms39676 KiB
31Wrong answer133ms17204 KiB
32Wrong answer171ms28720 KiB
33Wrong answer259ms33072 KiB
34Wrong answer210ms39240 KiB