| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 806685 |
2023-08-04T08:48:58 Z |
Tunglam07 |
Bajka (COCI20_bajka) |
C++17 |
|
24 ms |
980 KB |
#include<bits/stdc++.h>
using namespace std;
long long n, m, minn = INT_MAX, pre[301][301];
string s, t;
vector<int> ch[27];
long long backtrack(int id, int pos)
{
if(pre[id][pos])
{
return pre[id][pos];
}
if(pos == m)
{
return 0;
}
long long ans = INT_MAX;
for(int i : ch[s[id] - 96])
{
if(i < n - 1 && s[i + 1] == t[pos])
{
ans = min(ans, backtrack(i + 1, pos + 1) + abs(id - i) + 1);
}
if(i > 0 && s[i - 1] == t[pos])
{
ans = min(ans, backtrack(i - 1, pos + 1) + abs(id - i) + 1);
}
}
pre[id][pos] = ans;
return ans;
}
int main()
{
cin >> n >> m;
cin>> s;
cin>> t;
for(int i = 0; i < n; i++)
{
ch[s[i] - 96].push_back(i);
}
for(int c : ch[t[0] - 96])
{
minn = min(minn, backtrack(c, 1));
}
if(minn < INT_MAX)
{
cout << minn;
return 0;
}
cout << -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
2 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
3 ms |
980 KB |
Output is correct |
| 8 |
Correct |
18 ms |
952 KB |
Output is correct |
| 9 |
Correct |
24 ms |
980 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
980 KB |
Output is correct |
