Submission #74658601

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,2> a2;
typedef array<ll,3> a3;
ll n,m,k;
int a[N];
string S,T;

ll ne[N][26];


void __(){
    cin>>S>>T;
    n=S.size(),m=T.size();
    S=" "+S,T=" "+T;
    for(int i=0;i<26;i++){
        ne[n+1][i]=n+1;
        ne[n][i]=n+1;
    }

    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++) ne[i][j]=ne[i+1][j];
        ne[i][S[i+1]-'a']=i+1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll now=i-1;
        for(int j=1;j<=m;j++){
            int t=T[j]-'a';
            now=ne[now][t];
            now=min(now,n+1);
        }
        ans+=(n-now+1);
    }
    cout<<n*(n+1)/2-ans<<endl;
    // dp[0][0]=1;
    // for(int i=1;i<=n;i++){
    //     dp[i][0]=1;
    //     for(int j=1;j<=m;j++){

    //     }
    // }
}   


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

Submission Info

Submission Time
Task D - No-Subsequence Substring
User zhishengie
Language C++23 (GCC 15.2.0)
Score 400
Code Size 1045 Byte
Status AC
Exec Time 48 ms
Memory 44560 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 56
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3688 KiB
00_sample_01.txt AC 1 ms 3520 KiB
00_sample_02.txt AC 1 ms 3624 KiB
01_random_03.txt AC 25 ms 29056 KiB
01_random_04.txt AC 30 ms 30568 KiB
01_random_05.txt AC 13 ms 18284 KiB
01_random_06.txt AC 15 ms 17492 KiB
01_random_07.txt AC 16 ms 24916 KiB
01_random_08.txt AC 32 ms 44496 KiB
01_random_09.txt AC 39 ms 44428 KiB
01_random_10.txt AC 33 ms 44484 KiB
01_random_11.txt AC 44 ms 44392 KiB
01_random_12.txt AC 22 ms 44476 KiB
01_random_13.txt AC 22 ms 44488 KiB
01_random_14.txt AC 35 ms 44408 KiB
01_random_15.txt AC 36 ms 44476 KiB
01_random_16.txt AC 42 ms 44400 KiB
01_random_17.txt AC 35 ms 44400 KiB
01_random_18.txt AC 23 ms 44332 KiB
01_random_19.txt AC 45 ms 44408 KiB
01_random_20.txt AC 34 ms 44472 KiB
01_random_21.txt AC 24 ms 44388 KiB
01_random_22.txt AC 41 ms 44480 KiB
01_random_23.txt AC 43 ms 44560 KiB
01_random_24.txt AC 40 ms 44408 KiB
01_random_25.txt AC 48 ms 44396 KiB
01_random_26.txt AC 31 ms 44412 KiB
01_random_27.txt AC 36 ms 44440 KiB
01_random_28.txt AC 39 ms 44468 KiB
01_random_29.txt AC 37 ms 44332 KiB
01_random_30.txt AC 34 ms 44408 KiB
01_random_31.txt AC 35 ms 44392 KiB
01_random_32.txt AC 20 ms 44472 KiB
01_random_33.txt AC 39 ms 44468 KiB
01_random_34.txt AC 37 ms 44544 KiB
01_random_35.txt AC 44 ms 44484 KiB
01_random_36.txt AC 41 ms 44400 KiB
01_random_37.txt AC 35 ms 44440 KiB
01_random_38.txt AC 34 ms 44400 KiB
01_random_39.txt AC 34 ms 44408 KiB
01_random_40.txt AC 26 ms 40292 KiB
01_random_41.txt AC 34 ms 36028 KiB
01_random_42.txt AC 35 ms 38824 KiB
01_random_43.txt AC 9 ms 16276 KiB
01_random_44.txt AC 28 ms 33388 KiB
01_random_45.txt AC 7 ms 10988 KiB
01_random_46.txt AC 37 ms 38708 KiB
01_random_47.txt AC 20 ms 22796 KiB
01_random_48.txt AC 7 ms 16396 KiB
01_random_49.txt AC 24 ms 30360 KiB
01_random_50.txt AC 21 ms 37380 KiB
01_random_51.txt AC 41 ms 44440 KiB
01_random_52.txt AC 18 ms 44540 KiB
01_random_53.txt AC 1 ms 3524 KiB
01_random_54.txt AC 1 ms 3600 KiB
01_random_55.txt AC 1 ms 3528 KiB