oj.uz

Submission #470330

# Submission time Handle Problem Language Result Execution time Memory
470330 2021-09-03T13:44:50 Z mychecksedad Bajka (COCI20_bajka) C++17
70 / 70
 56 ms 672 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 310, F = 1e9;


int n, m, dp[N][N], ans = F;
string s, t;

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> m >> s >> t;
	for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) dp[i][j] = F;
	s = ' ' + s + ' ';
	t = ' ' + t + ' ';
	for(int i = 1; i <= m; i++){
		vector<int> v;
		for(int j = 1; j <= n; j++) if(s[j] == t[i]) v.pb(j);
		for(int pos: v){
			dp[i][pos] = (i==1?0:F);
			if(i > 1){
				if(s[pos - 1] == t[i - 1]){
					dp[i][pos] = min(dp[i][pos], dp[i - 1][pos - 1] + 1);
				}
				if(s[pos + 1] == t[i - 1]){
					dp[i][pos] = min(dp[i][pos], dp[i - 1][pos + 1] + 1);
				}
			}
		}
		for(int j = 0; j < v.size(); j++){
			for(int k = 0; k < v.size(); k++){
				dp[i][v[j]] = min(dp[i][v[j]], abs(v[j] - v[k]) + dp[i][v[k]]);
			}
			if(i == m){
				ans = min(ans, dp[i][v[j]]);
			}
		}
	}
	cout << (ans==F ? -1 : ans);

	return 0;
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int j = 0; j < v.size(); j++){
      |                  ~~^~~~~~~~~~
bajka.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int k = 0; k < v.size(); k++){
      |                   ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 332 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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 5 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 8 ms 588 KB Output is correct
8 Correct 29 ms 588 KB Output is correct
9 Correct 56 ms 672 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 6 ms 588 KB Output is correct