| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 344144 |
2021-01-05T07:47:56 Z |
Nursik |
Bajka (COCI20_bajka) |
C++14 |
|
97 ms |
1280 KB |
#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;
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];
int add = 1e9;
if (pos - 1 >= 0 && a[pos - 1] == b[le])
add = min(add, rec(pos - 1, le + 1) + 1);
if (pos + 1 < a.size() && a[pos + 1] == b[le])
add = min(add, rec(pos + 1, le + 1) + 1);
for (int i = 0; i < g[a[pos] - 'a'].size(); i++)
{
int to = g[a[pos] - 'a'][i];
if (to != pos && (to - 1 >= 0 && a[to - 1] == b[le]))
{
add = min(add, rec(to - 1, le + 1) + abs(to - pos) + 1);
}
if (to != pos && (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);
}
int 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
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:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (pos + 1 < a.size() && a[pos + 1] == b[le])
| ~~~~~~~~^~~~~~~~~~
bajka.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < g[a[pos] - 'a'].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:44:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if (to != pos && (to + 1 < a.size() && a[to + 1] == b[le]))
| ~~~~~~~^~~~~~~~~~
bajka.cpp: In function 'int main()':
bajka.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
bajka.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
640 KB |
Output is correct |
| 7 |
Correct |
17 ms |
1132 KB |
Output is correct |
| 8 |
Correct |
79 ms |
1260 KB |
Output is correct |
| 9 |
Correct |
97 ms |
1260 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1132 KB |
Output is correct |
