oj.uz

Submission #720598

# Submission time Handle Problem Language Result Execution time Memory
720598 2023-04-08T15:13:12 Z trucmai Bajka (COCI20_bajka) C++17
70 / 70
 97 ms 1576 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;

ll n,m,f[400][400]; 
string a,b; 

//f[i][j] 

ll dp(ll i,ll j){
  if(j == m) return 0; 
  ll &res = f[i][j];
  if(res != -1) return res;
  res = INF;
  for(ll k = 0;k < n;++k)
    if(a[k] == a[i])
      for(ll p = -1;p < 2;++p){
        if(!p || k + p < 0 || k + p >= n) continue; 
        if(a[k + p] != b[j]) continue; 
        res = min(res,dp(k+p,j+1) + abs(k - i) + 1);      
      }
  return res; 
}

void solve(){
  cin>>n>>m>>a>>b;
  mset(f,-1);
  ll ans = INF;
  for(ll i = 0;i < n;++i)
    if(a[i] == b[0]) ans = min(ans,dp(i,1));
  cout<<(ans >= INF ? -1 : ans);
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  //freopen("i.inp","r",stdin);
  //freopen("o.out","w",stdout);
  ll t = 1; //cin>>t; 
  while(t--) solve();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1480 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 13 ms 1484 KB Output is correct
8 Correct 97 ms 1576 KB Output is correct
9 Correct 91 ms 1576 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 8 ms 1480 KB Output is correct