Submission #477994

#	Time	Username	Problem	Language	Result	Execution time	Memory
477994		manh2004	Bajka (COCI20_bajka)	C++14	70 / 70	60 ms	692 KiB

bajka

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)

const int MAXN = 305;
const int inf = 1000000;

int n, m, dp[MAXN][MAXN];
char s[MAXN], p[MAXN];

int rek(int a, int b) {
  if (b == m) return 0;
  if (dp[a][b] != -1) return dp[a][b];
  int ret = inf;
  REP(i, n) {
    if (s[i] == s[a]) {
      FOR(j, -1, 2) {
        if (!j || i + j < 0 || i + j >= n) continue;
        if (s[i + j] != p[b]) continue;
        ret = min(ret, rek(i + j, b + 1) + abs(i - a) + 1);
      }
    }
  }
  return dp[a][b] = ret;
}

int main() {
  scanf("%d %d",&n,&m);
  scanf("%s",s);
  scanf("%s",p);
  memset(dp, -1, sizeof dp);
  int sol = inf;
  REP(i, n) if (s[i] == p[0]) sol = min(sol, rek(i, 1));
  if (sol >= inf) sol = -1;
  printf("%d\n",sol);
  return 0;
}

Compilation message (stderr)

bajka.cpp: In function 'int main()':
bajka.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d %d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~~
bajka.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%s",s);
      |   ~~~~~^~~~~~~~
bajka.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%s",p);
      |   ~~~~~^~~~~~~~

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