Submission #705783

#TimeUsernameProblemLanguageResultExecution timeMemory
705783AbitoBajka (COCI20_bajka)C++17
70 / 70
61 ms1236 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt #define int long long typedef unsigned long long ull; using namespace std; const int N=305; int dp[N][N],n,m; char a[N],b[N]; bool vis[N][N]; vector<int> adj[30]; set<char> s; int rec(int i,int j){ //cout<<i<<' '<<j<<endl; if (j==m) return 0; if (vis[i][j]) return dp[i][j]; vis[i][j]=true; dp[i][j]=INT_MAX; if (i>1){ if (a[i-1]==b[j+1]) dp[i][j]=min(dp[i][j],rec(i-1,j+1)+1); } if (i<n){ if (a[i+1]==b[j+1]) dp[i][j]=min(dp[i][j],rec(i+1,j+1)+1); } for (auto u:adj[a[i]-'a']) dp[i][j]=min(dp[i][j],rec(u,j)+abs(u-i)); return dp[i][j]; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for (int i=1;i<=n;i++){ cin>>a[i]; s.ep(a[i]); adj[a[i]-'a'].pb(i); } for (int j=1;j<=m;j++) cin>>b[j]; if (s.size()==n){ int idx=0; for(int i=1;i<=n;i++){ if(a[i]==b[1]) idx=i; } if(idx==0){ cout<<-1; return 0; } int ans=0; for(int i=2;i<=m;i++){ bool c=0; if(idx+1<=m && a[idx+1]==b[i]){ ans++; c=1; idx++; } else if(idx-1>=1 && a[idx-1]==b[i]){ ans++; c=1; idx--; } if(!c){ cout<<-1; return 0; } } cout<<ans; return 0; } int ans=INT_MAX; for (int i=1;i<=n;i++) ans=min(ans,rec(i,0)); if (ans>=INT_MAX) cout<<-1<<endl; else cout<<ans-1<<endl; return 0; }

Compilation message (stderr)

bajka.cpp: In function 'int32_t main()':
bajka.cpp:44:17: warning: comparison of integer expressions of different signedness: 'std::set<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |     if (s.size()==n){
      |         ~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...