Submission #18766349

Source Code Expand

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

int dp[1001][1001];
const int INF = 1e9;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,j;
    cin>>n>>m;
    int a[n+1],b[m+1];
    for (int i=1;i<=n;++i)
        cin>>a[i];
    for (int i=1;i<=m;++i)
        cin>>b[i];
    for (int i=0;i<=n;++i)
        for (int j=0;j<=m;++j)
            dp[i][j]=max(i,j);
    for (int k=2;k<=n+m;++k)
        for (int i=1;i<=n&&i<k;++i)
            if (k-i<=m)
            {
                j=k-i;
                if (a[i]==b[j])
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i][j]),min(dp[i-1][j]+1,dp[i][j-1]+1));
                else
                    dp[i][j]=min(min(dp[i-1][j-1]+1,dp[i][j]),min(dp[i-1][j]+1,dp[i][j-1]+1));
            }
    cout<<dp[n][m];
    return 0;
}

Submission Info

Submission Time
Task E - Sequence Matching
User ScarletS
Language C++ (GCC 9.2.1)
Score 500
Code Size 829 Byte
Status AC
Exec Time 20 ms
Memory 7544 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All extreme_00.txt, extreme_01.txt, extreme_02.txt, extreme_03.txt, extreme_04.txt, extreme_05.txt, extreme_06.txt, handmade_00.txt, handmade_01.txt, pattern_00.txt, pattern_01.txt, pattern_02.txt, pattern_03.txt, pattern_04.txt, pattern_05.txt, pattern_06.txt, pattern_07.txt, pattern_08.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
extreme_00.txt AC 15 ms 7348 KiB
extreme_01.txt AC 16 ms 7484 KiB
extreme_02.txt AC 16 ms 7416 KiB
extreme_03.txt AC 16 ms 7464 KiB
extreme_04.txt AC 20 ms 7488 KiB
extreme_05.txt AC 2 ms 3560 KiB
extreme_06.txt AC 3 ms 7344 KiB
handmade_00.txt AC 2 ms 3500 KiB
handmade_01.txt AC 2 ms 3548 KiB
pattern_00.txt AC 14 ms 7464 KiB
pattern_01.txt AC 15 ms 7492 KiB
pattern_02.txt AC 16 ms 7540 KiB
pattern_03.txt AC 6 ms 5792 KiB
pattern_04.txt AC 2 ms 3800 KiB
pattern_05.txt AC 3 ms 4892 KiB
pattern_06.txt AC 10 ms 5948 KiB
pattern_07.txt AC 5 ms 4292 KiB
pattern_08.txt AC 9 ms 6124 KiB
random_00.txt AC 19 ms 7492 KiB
random_01.txt AC 20 ms 7544 KiB
random_02.txt AC 17 ms 7468 KiB
random_03.txt AC 2 ms 3868 KiB
random_04.txt AC 2 ms 3716 KiB
random_05.txt AC 4 ms 4876 KiB
random_06.txt AC 10 ms 5936 KiB
random_07.txt AC 5 ms 4272 KiB
random_08.txt AC 7 ms 6124 KiB
random_09.txt AC 11 ms 7164 KiB
sample_01.txt AC 3 ms 3548 KiB
sample_02.txt AC 2 ms 3560 KiB
sample_03.txt AC 2 ms 3544 KiB