# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
448139 |
2021-07-29T03:18:36 Z |
jk410 |
Bajka (COCI20_bajka) |
C++17 |
|
113 ms |
696 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int N,M,Ans=INF;
int D[300][300];
string A,B;
int d(int idx,int to){
if (to==M)
return 0;
int &r=D[idx][to];
if (r!=-1)
return r;
r=INF;
for (int i=0; i<N; i++){
if (A[i]!=A[idx])
continue;
for (int j:{-1,1}){
if (i+j<0||i+j==N||A[i+j]!=B[to])
continue;
r=min(r,d(i+j,to+1)+abs(idx-i)+1);
}
}
return r;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(D,-1,sizeof(D));
cin>>N>>M>>A>>B;
for (int i=0; i<N; i++){
if (A[i]==B[0])
Ans=min(Ans,d(i,1));
}
if (Ans==INF)
cout<<-1;
else
cout<<Ans;
return 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 |
672 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 |
668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 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 |
12 ms |
696 KB |
Output is correct |
8 |
Correct |
101 ms |
680 KB |
Output is correct |
9 |
Correct |
113 ms |
672 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
7 ms |
588 KB |
Output is correct |