Submission #344147

#TimeUsernameProblemLanguageResultExecution timeMemory
344147NursikBajka (COCI20_bajka)C++14
0 / 70
2 ms1220 KiB
#include <bits/stdc++.h> using namespace std; /* Rucode: jaqVYNrpMj JUDGE_ID: 295965SY dl:160532 */ void data() { #ifdef NURS freopen("main.in", "r", stdin); freopen("main.out", "w", stdout); #endif } void win() { ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0); } int n, m, add, ans; string a, b; int was[350][350], dp[350][350]; vector<int> g[30]; int rec(int pos, int le) { // cout << pos << " " << le << '\n'; if (le == b.size()) return 0; if (was[pos][le]) return dp[pos][le]; add = 1e9; for (int i = 0; i < g[a[pos] - 'a'].size(); i++) { int to = g[a[pos] - 'a'][i]; if (to - 1 >= 0 && a[to - 1] == b[le]) add = min(add, rec(to - 1, le + 1) + abs(to - pos) + 1); if (to + 1 < a.size() && a[to + 1] == b[le]) add = min(add, rec(to + 1, le + 1)+ abs(to - pos) + 1); } was[pos][le] = 1; dp[pos][le] = add; return add; } int main() { data(); win(); cin >> n >> m; cin >> a >> b; for (int i = 0; i < a.size(); i++) g[a[i] - 'a'].push_back(i); ans = 1e9; for (int i = 0; i < a.size(); i++) if (a[i] == b[0]) ans = min(ans, rec(i, 1)); ans += (ans == 1e9) * (-ans - 1); cout << ans; }

Compilation message (stderr)

bajka.cpp: In function 'int rec(int, int)':
bajka.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  if (le == b.size())
      |      ~~~^~~~~~~~~~~
bajka.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < g[a[pos] - 'a'].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if (to + 1 < a.size() && a[to + 1] == b[le])
      |       ~~~~~~~^~~~~~~~~~
bajka.cpp: In function 'int main()':
bajka.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
bajka.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...