# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
#define pii pair <int , int>
const int N = 305;
int idx1,anss[N][N],ans,cur,x,y,z,dist[N][N];
int n,m;
string s,s1;
vector < pair <int, int > > v[N];
vector <int> occ[N];
priority_queue < pair < int, pii > > q;
void go(int i, int cur) {
if (cur > 1) {
v[i].pb({cur - 1, abs(i-cur) + 1});//, cout<<i<<" "<<cur - 1<<" "<<abs(i-cur) +1<<endl;
}
if (cur < n) {
v[i].pb({cur + 1,abs(i - cur) + 1});//, cout<<i<<" "<<cur + 1<<" "<<abs(i - cur) + 1<<endl;
}
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
cin>>s>>s1;
s ="@" + s;
for (int i = 1; i <= n; i++) {
occ[s[i]-'a'].pb(i);
}
for (int i = 1; i <= n; i++) {
if (i > 1)
v[i].pb({i - 1, 1});
if (i < n) v[i].pb({i+1,1});
for (int j = 0; j < occ[s[i]-'a'].size(); j++) {
cur = occ[s[i]-'a'][j];
if (cur == i) continue;
go(i,cur);
}
}
for (int i = 1; i <= n; i++) {
for (int j= 1; j <= m; j++) {
dist[i][j] = 1e9;
}
}
s1 = "@" + s1;
ans = 1e9;
for (int i = 0; i < occ[s1[1]-'a'].size(); i++) {
q.push({0,{occ[s1[1]-'a'][i],1}});
dist[occ[s1[1]-'a'][i]][1] = 0;
}
while (!q.empty()) {
x = -(q.top().f);
y= q.top().s.f;
z = q.top().s.s;
//cout<<x<<" "<<y<<" "<<z<<endl;
if (z == m) ans = min(ans,x);
q.pop();
if (dist[y][z] < x) continue;
for (int j = 0; j < v[y].size(); j++) {
int nxtid = v[y][j].f;
if(s[nxtid] == s1[z + 1] && dist[nxtid][z+1] > dist[y][z] + v[y][j].s) {
q.push({-(dist[y][z] + v[y][j].s), {nxtid,z+1}});
dist[nxtid][z+1] = dist[y][z] + v[y][j].s;
}
}
}
if (ans >= 1e9) cout<<-1<<endl;
else
cout<<ans<<endl;
}
Compilation message
bajka.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
22 | main() {
| ^~~~
bajka.cpp: In function 'int main()':
bajka.cpp:34:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int j = 0; j < occ[s[i]-'a'].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0; i < occ[s1[1]-'a'].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:60:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j = 0; j < v[y].size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
972 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 3 |
Correct |
1 ms |
844 KB |
Output is correct |
| 4 |
Correct |
1 ms |
972 KB |
Output is correct |
| 5 |
Correct |
1 ms |
716 KB |
Output is correct |
| 6 |
Correct |
1 ms |
716 KB |
Output is correct |
| 7 |
Correct |
18 ms |
1472 KB |
Output is correct |
| 8 |
Correct |
120 ms |
2812 KB |
Output is correct |
| 9 |
Correct |
58 ms |
3372 KB |
Output is correct |
| 10 |
Correct |
1 ms |
716 KB |
Output is correct |
| 11 |
Correct |
10 ms |
1228 KB |
Output is correct |
