oj.uz

Submission #476299

# Submission time Handle Problem Language Result Execution time Memory
476299 2021-09-26T01:28:44 Z Mackerel_Pike Bajka (COCI20_bajka) C++14
70 / 70
 2 ms 588 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 305;

int n, m;
int f[maxn][maxn], lst[maxn], pre[maxn], nxt[maxn];
char s[maxn], t[maxn];

int main(){
  //freopen("bajka.in", "r", stdin);
  
  scanf("%d%d", &n, &m);
  scanf("%s", s);
  scanf("%s", t);

  memset(lst, -1, sizeof(lst));
  for(int i = 0; i < n; ++i)
    pre[i] = lst[s[i]], lst[s[i]] = i;
  memset(lst, -1, sizeof(lst));
  for(int i = n - 1; i >= 0; --i)
    nxt[i] = lst[s[i]], lst[s[i]] = i;
  
  memset(f, 0x3f, sizeof(f));
  for(int i = 0; i < n; ++i)
    f[(s[i] == t[0])][i] = 0;
  for(int i = 0; i < m; ++i){
    for(int j = 0; j < n; ++j)
      if(~pre[j])
	f[i][j] = min(f[i][j], f[i][pre[j]] + j - pre[j]);
    for(int j = n - 1; j >= 0; --j)
      if(~nxt[j])
	f[i][j] = min(f[i][j], f[i][nxt[j]] + nxt[j] - j);
    for(int j = 0; j < n; ++j){
      if(j && s[j - 1] == t[i])
	f[i + 1][j - 1] = min(f[i + 1][j - 1], f[i][j] + 1);
      if(j < n && s[j + 1] == t[i])
	f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + 1);
    }
  }

  int ans = 0x3f3f3f3f;
  for(int j = 0; j < n; ++j)
    ans = min(ans, f[m][j]);
  printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
  return 0;
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:20:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |     pre[i] = lst[s[i]], lst[s[i]] = i;
      |                  ~~~^
bajka.cpp:20:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |     pre[i] = lst[s[i]], lst[s[i]] = i;
      |                             ~~~^
bajka.cpp:23:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |     nxt[i] = lst[s[i]], lst[s[i]] = i;
      |                  ~~~^
bajka.cpp:23:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |     nxt[i] = lst[s[i]], lst[s[i]] = i;
      |                             ~~~^
bajka.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
bajka.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~
bajka.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%s", t);
      |   ~~~~~^~~~~~~~~

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 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
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct