oj.uz

Submission #315738

# Submission time Handle Problem Language Result Execution time Memory
315738 2020-10-23T20:49:25 Z DanerZein Bajka (COCI20_bajka) C++14
70 / 70
 147 ms 1152 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1088 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 1 ms 1024 KB Output is correct
6 Correct 1 ms 1024 KB Output is correct
7 Correct 13 ms 1152 KB Output is correct
8 Correct 77 ms 1144 KB Output is correct
9 Correct 147 ms 1144 KB Output is correct
10 Correct 1 ms 1024 KB Output is correct
11 Correct 7 ms 1152 KB Output is correct