| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 485560 |
2021-11-08T09:18:33 Z |
groupATSU |
Bajka (COCI20_bajka) |
C++14 |
|
31 ms |
1296 KB |
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#define aldgebu return
#define ff first
#define sc second
#define pb push_back
#define pii pair <int,int>
#define p push
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
void Dontfuckedup(){
int dp[501][501];
for (int i = 0; i <= 500; i++)
for (int j = 0; j <= 500; j++)
dp[i][j] = inf;
int M, N;
string s1, s;
cin >> M >> N >> s1 >> s;
vector <int> pos[26];
for (int i = 0; i < M; i++)
pos[s1[i] - 'a'].pb(i);
int cur = s[0] - 'a';
for (int i = 0; i < pos[cur].size(); i++){
dp[pos[cur][i]][0] = 0;
}
int val, lst;
vector <int> v;
for (int i = 1; i < N; i++){
cur = s[i] - 'a';
lst = s[i - 1] - 'a';
v.clear();
for (int j = 0; j < pos[cur].size(); j++){
val = pos[cur][j];
if (val - 1 >= 0 && s1[val - 1] == s[i - 1])
v.pb(val - 1);
if (val + 1 < M && s1[val + 1] == s[i - 1])
v.pb(val + 1);
}
for (int j = 0; j < v.size(); j++){
for (int k = 0; k < pos[lst].size(); k++){
dp[v[j]][i - 1] = min(dp[v[j]][i - 1], dp[pos[lst][k]][i - 1] + abs(pos[lst][k] - v[j]));
}
}
for (int j = 0; j < pos[cur].size(); j++){
val = pos[cur][j];
if (val - 1 >= 0 && s1[val - 1] == s[i - 1])
dp[pos[cur][j]][i] = min(dp[pos[cur][j]][i], dp[val - 1][i - 1] + 1);
if (val + 1 < M && s1[val + 1] == s[i - 1])
dp[pos[cur][j]][i] = min(dp[pos[cur][j]][i], dp[val + 1][i - 1] + 1);
}
}
int ans = inf;
cur = s[N - 1] - 'a';
for (int i = 0; i < pos[cur].size(); i++){
ans = min(ans, dp[pos[cur][i]][N - 1]);
}
cout << (ans == inf ? -1 : ans);
}
int32_t main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1; //cin >> T;
while (T--)Dontfuckedup();
return 0;
}
Compilation message
bajka.cpp: In function 'void Dontfuckedup()':
bajka.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < pos[cur].size(); i++){
| ~~^~~~~~~~~~~~~~~~~
bajka.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j = 0; j < pos[cur].size(); j++){
| ~~^~~~~~~~~~~~~~~~~
bajka.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int j = 0; j < v.size(); j++){
| ~~^~~~~~~~~~
bajka.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int k = 0; k < pos[lst].size(); k++){
| ~~^~~~~~~~~~~~~~~~~
bajka.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int j = 0; j < pos[cur].size(); j++){
| ~~^~~~~~~~~~~~~~~~~
bajka.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < pos[cur].size(); i++){
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1292 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1296 KB |
Output is correct |
| 8 |
Correct |
15 ms |
1228 KB |
Output is correct |
| 9 |
Correct |
31 ms |
1228 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1228 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1228 KB |
Output is correct |
