Submission #589100

#TimeUsernameProblemLanguageResultExecution timeMemory
589100IwanttobreakfreeBajka (COCI20_bajka)C++98
20 / 70
202 ms688 KiB
#include <iostream> #include <vector> using namespace std; void 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; if(t[j]!=s[i])return; for(int x:word[s[i]-'a']){ if(x-1!=i&&x&&s[x-1]==t[j+1]){ if(dp[x-1][j+1]>dp[i][j]+max(x-1-i,i-x+1)){ dp[x-1][j+1]=dp[i][j]+max(x-1-i,i-x+1); DP(n,m,x-1,j+1,dp,word,s,t); } } if(x+1!=i&&x<n-1&&s[x+1]==t[j+1]){ if(dp[x+1][j+1]>dp[i][j]+max(x+1-i,i-x-1)){ dp[x+1][j+1]=dp[i][j]+max(x+1-i,i-x-1); DP(n,m,x+1,j+1,dp,word,s,t); } } } } 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); for(int x:word[t[0]-'a']){ dp[x][0]=0; DP(n,m,x,0,dp,word,s,t); } int ans=1e9; for(int i=0;i<n;i++)ans=min(ans,dp[i][m-1]); if(ans==1e9)cout<<-1; else cout<<ans; }

Compilation message (stderr)

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