oj.uz

Submission #477994

# Submission time Handle Problem Language Result Execution time Memory
477994 2021-10-05T02:16:13 Z manh2004 Bajka (COCI20_bajka) C++14
70 / 70
 60 ms 692 KB 
#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

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

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 12 ms 592 KB Output is correct
8 Correct 60 ms 672 KB Output is correct
9 Correct 48 ms 668 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 7 ms 692 KB Output is correct