Submission #1118905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118905		hamzabc	Round words (IZhO13_rowords)	C++14	16 / 100	240 ms	22392 KiB

rowords

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'
 

int asz;
int bsz;
string a, b;
vector<vector<int>> memoization;


long long int dp(int sa, int sb){
	if (sa == a.size() || sb == b.size())
		return 0;
	if (memoization[sa][sb] != -1)
		return memoization[sa][sb];
	dp(sa, sb + 1); dp(sa + 1, sb);
	if (a[sa] == b[sb])
		memoization[sa][sb] = dp(sa + 1, sb + 1) + 1;
	else
		memoization[sa][sb] = max(dp(sa, sb + 1), dp(sa + 1, sb));
	return memoization[sa][sb];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> a >> b;
	asz = a.size();
	bsz = b.size();
	a += a;
	b += b;
	memoization.resize(a.size() + 1, vector<int>(b.size() + 1, -1));
	dp(0, 0);
	int res = 0;
	for (int i = 0; i <= asz * 2; i++){
		memoization[i][bsz * 2] = 0;
	}
	for (int i = 0; i <= bsz * 2; i++){
		memoization[asz * 2][i] = 0;
	}
	for (int i = 0; i < asz; i++){
		for (int o = 0; o < bsz; o++){
			if (a[i + asz] == b[i + bsz] && memoization[i + asz][o + bsz] == memoization[i][o + bsz] && memoization[i + asz][o + bsz] == memoization[i + asz][o]){
				res = max(res, memoization[i][o] - memoization[i + asz][o + bsz]);
			}
		}
	}
	string aeski = a;
	a = "";
	for (int i = asz * 2 - 1; i >= 0; i--)
		a = a + aeski[i];
	for (int i = 0; i < a.size() + 1; i++)
		fill(all(memoization[i]), -1);
	dp(0, 0);
	for (int i = 0; i <= asz * 2; i++){
		memoization[i][bsz * 2] = 0;
	}
	for (int i = 0; i <= bsz * 2; i++){
		memoization[asz * 2][i] = 0;
	}
	for (int i = 0; i < asz; i++){
		for (int o = 0; o < bsz; o++){
			if (a[i + asz] == b[i + bsz] && memoization[i + asz][o + bsz] == memoization[i][o + bsz] && memoization[i + asz][o + bsz] == memoization[i + asz][o])
				res = max(res, memoization[i][o] - memoization[i + asz][o + bsz]);
		}
	}
	cout << res;
	return 0;
}

Compilation message (stderr)

rowords.cpp: In function 'long long int dp(int, int)':
rowords.cpp:20:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  if (sa == a.size() || sb == b.size())
      |      ~~~^~~~~~~~~~~
rowords.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  if (sa == a.size() || sb == b.size())
      |                        ~~~^~~~~~~~~~~
rowords.cpp: In function 'int main()':
rowords.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < a.size() + 1; i++)
      |                  ~~^~~~~~~~~~~~~~

• Subtask 1: 16 / 100