Submission #589145

#	Time	Username	Problem	Language	Result	Execution time	Memory
589145		Iwanttobreakfree	Bajka (COCI20_bajka)	C++98	70 / 70	108 ms	700 KiB

bajka

#include <iostream>
#include <vector>
using namespace std;
int DP(int n,int m,int i,int j,vector<vector<int>>& dp,vector<vector<int>>& word,string& s,string& t){
    if(j==m-1)return 0;
    if(dp[i][j]!=1e9)return dp[i][j];
    int ans=1e9;
    for(int x:word[s[i]-'a']){
        if(x&&s[x-1]==t[j+1]){
            ans=min(DP(n,m,x-1,j+1,dp,word,s,t)+1+max(x-i,i-x),ans);
        }
        if(x<n-1&&s[x+1]==t[j+1]){
            ans=min(DP(n,m,x+1,j+1,dp,word,s,t)+1+max(x-i,i-x),ans);
        }
    }
    if(ans==1e9)return dp[i][j]=ans+1;
    return dp[i][j]=ans;
}
int main(){
    int n,m;
    string s,t;
    cin>>n>>m>>s>>t;
    vector<vector<int>> dp(n,vector<int>(m+1,1e9)),word(26,vector<int>());
    for(int i=0;i<s.size();i++)word[s[i]-'a'].push_back(i);
    int ans=1e9;
    for(int x:word[t[0]-'a']){
        ans=min(DP(n,m,x,0,dp,word,s,t),ans);
    }
    if(ans>=1e9)cout<<-1;
    else cout<<ans;
}

Compilation message (stderr)

bajka.cpp: In function 'int main()':
bajka.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<s.size();i++)word[s[i]-'a'].push_back(i);
      |                 ~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50