| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1011853 |
2024-07-01T09:50:15 Z |
Dedibeat |
Bajka (COCI20_bajka) |
C++17 |
|
1 ms |
1116 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
int dp[n+5][m+5];
map<char, vector<int> > mp;
for(int i = 0; i<n; i++) mp[a[i]].push_back(i);
for(int i = 0; i<=m; i++){
for(int j = 0; j<n; j++) dp[i][j] = 1e10;
}
for(int j = 0; j<n; j++) {
if(a[j] == b[0]) dp[0][j] = 0;
}
for(int i = 1; i<m; i++){
for(int j = 0; j<n; j++){
if(a[j] == b[i]) {
// cout << j << endl;
if(j > 0) {
char x = a[j-1];
auto v = mp[x];
for(auto k : v){
int cost = abs((j - 1) - k);
dp[i][j] = min(dp[i-1][k] + cost, dp[i][j]);
}
}
if(j < n-1) {
char x = a[j + 1];
auto v = mp[x];
for(auto k : v){
int cost = abs((j + 1) - k);
dp[i][j] = min(dp[i-1][k] + cost, dp[i][j]);
}
}
}
// cout << dp[i][j] << " ";
}
int mn = 1e10;
for(auto k : mp[b[m-1]]){
mn = min(dp[m-1][k] , mn);
}
if(mn >= 1e10) {
cout << "-1\n";
return 0;
}
cout << mn + m - 1 << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
