답안 #344144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344144 2021-01-05T07:47:56 Z Nursik Bajka (COCI20_bajka) C++14
70 / 70
97 ms 1280 KB
#include <bits/stdc++.h>
using namespace std; 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
} 
void win()
{	
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
}

int n, m;
string a, b;
int was[350][350], dp[350][350];
vector<int> g[30];
int rec(int pos, int le)
{
//	cout << pos << " " << le << '\n';
	if (le == b.size())
		return 0;
	if (was[pos][le])
		return dp[pos][le];

	int add = 1e9;
	if (pos - 1 >= 0 && a[pos - 1] == b[le])
		add = min(add, rec(pos - 1, le + 1) + 1);
	if (pos + 1 < a.size() && a[pos + 1] == b[le])
		add = min(add, rec(pos + 1, le + 1) + 1);
	for (int i = 0; i < g[a[pos] - 'a'].size(); i++)
	{
		int to = g[a[pos] - 'a'][i];
		if (to != pos && (to - 1 >= 0 && a[to - 1] == b[le]))
		{
			add = min(add, rec(to - 1, le + 1) + abs(to - pos) + 1);
		}
		if (to != pos && (to + 1 < a.size() && a[to + 1] == b[le]))
		{
			add = min(add, rec(to + 1, le + 1)+ abs(to - pos) + 1);	
		}
	}
	was[pos][le] = 1;
	dp[pos][le] = add;
	return add;
}
int main()
{
	data();
	win();      
	cin >> n >> m;
	cin >> a >> b;
	for (int i = 0; i < a.size(); i++)
	{
		g[a[i] - 'a'].push_back(i);
	}	
	int ans = 1e9;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] == b[0])
		{
			ans = min(ans, rec(i, 1));	
		}
	}
	ans += (ans == 1e9) * (-ans - 1);
	cout << ans;
}

Compilation message

bajka.cpp: In function 'int rec(int, int)':
bajka.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  if (le == b.size())
      |      ~~~^~~~~~~~~~~
bajka.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  if (pos + 1 < a.size() && a[pos + 1] == b[le])
      |      ~~~~~~~~^~~~~~~~~~
bajka.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < g[a[pos] - 'a'].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:44:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if (to != pos && (to + 1 < a.size() && a[to + 1] == b[le]))
      |                     ~~~~~~~^~~~~~~~~~
bajka.cpp: In function 'int main()':
bajka.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
bajka.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1280 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 17 ms 1132 KB Output is correct
8 Correct 79 ms 1260 KB Output is correct
9 Correct 97 ms 1260 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 5 ms 1132 KB Output is correct