Submission #315738

#	Time	Username	Problem	Language	Result	Execution time	Memory
315738		DanerZein	Bajka (COCI20_bajka)	C++14	70 / 70	147 ms	1152 KiB

bajka

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
const ll MAX=1e12;
ll n,m;
ll dp[310][310];
string x,y;
map<ll,vi> mvi;
ll scary(ll i,ll j){
  if(dp[i][j]!=-1) return dp[i][j];
  if(j==m) return 0;
  ll ans=MAX;
  if(i+1<n && x[i+1]==y[j]){
    for(ll k=0;k<mvi[y[j]].size();k++){
      ll rp=mvi[y[j]][k];
      ll dis=abs((i+1)-rp);
      ans=min(ans,scary(rp,j+1)+dis+1);
    }
  }
  if(i-1>=0 && x[i-1]==y[j]){
    for(ll k=0;k<mvi[y[j]].size();k++){
      ll rp=mvi[y[j]][k];
      ll dis=abs((i-1)-rp);
      ans=min(ans,scary(rp,j+1)+dis+1);
    }
  }
  return dp[i][j]=ans;
}
int main(){
  cin>>n>>m;
  cin>>x>>y;
  ll ans=MAX;
  memset(dp,-1,sizeof dp);
  for(ll i=0;i<x.size();i++) mvi[x[i]].push_back(i);
  for(ll i=0;i<x.size();i++){
    if(x[i]==y[0])
      ans=min(ans,scary(i,1));
  }
  if(ans==MAX) ans=-1;
  cout<<ans<<endl;
}

Compilation message (stderr)

bajka.cpp: In function 'll scary(ll, ll)':
bajka.cpp:15:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(ll k=0;k<mvi[y[j]].size();k++){
      |                ~^~~~~~~~~~~~~~~~~
bajka.cpp:22:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(ll k=0;k<mvi[y[j]].size();k++){
      |                ~^~~~~~~~~~~~~~~~~
bajka.cpp: In function 'int main()':
bajka.cpp:35:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(ll i=0;i<x.size();i++) mvi[x[i]].push_back(i);
      |              ~^~~~~~~~~
bajka.cpp:36:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(ll i=0;i<x.size();i++){
      |              ~^~~~~~~~~

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