Submission #1121736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121736		hamzabc	Round words (IZhO13_rowords)	C++14	8 / 100	206 ms	131072 KiB

rowords

#include <bits/stdc++.h>


using namespace std;


#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'

#ifdef L
ifstream input("input.txt");
#define cin input
#else
// #define USACO
#ifdef USACO
ifstream input("newbarn.in");
ofstream output("newbarn.out");
#define cin input
#define cout output
#endif
#endif


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


int dp(int ka, int kb){
	if (ka >= asz || kb >= bsz)
		return 0;
	if (memoization[ka][kb] != -1)
		return memoization[ka][kb];
	if (a[ka] == b[kb]){
		memoization[ka][kb] = dp(ka + 1, kb + 1) + 1;
		direction[ka][kb][0].first = ka;
		direction[ka][kb][0].second = kb;
	}else{
		if (dp(ka + 1, kb) >= dp(ka, kb + 1)){
			memoization[ka][kb] = dp(ka + 1, kb);
			if (ka + 1 < asz && kb < bsz){
				direction[ka][kb][0].first = direction[ka + 1][kb][0].first;
				direction[ka][kb][0].second = direction[ka + 1][kb][0].second;
			}
		}else{
			memoization[ka][kb] = dp(ka, kb + 1);
			if (ka < asz && kb + 1 < bsz){
				direction[ka][kb][0].first = direction[ka][kb + 1][0].first;
				direction[ka][kb][0].second = direction[ka][kb + 1][0].second;
			}
		}
	}
	return memoization[ka][kb];
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> a >> b;
	if (a.size() > b.size())
		swap(a, b);
	b += b;
	b.pop_back();
	asz = a.size();
	bsz = b.size();
	vector<int> log2lst(b.size() * 2);
	for (int i = 1; i < bsz * 2; i++)
		log2lst[i] = log2lst[i / 2] + 1;
	memoization.resize(asz, vector<int>(b.size(), -1));
	direction.resize(asz, vector<vector<pair<int, int>>>(bsz, vector<pair<int, int>>(log2lst[bsz / 2] + 1, { -1, -1 })));
	dp(0, 0);
	for (int i = bsz - 1; i >= 0; i--){
		for (int o = asz - 1; o >= 0; o--){
			if (direction[o][i][0].first == -1)
				continue;
			for (int j = 0; j < log2lst[bsz / 2]; j++){
				auto d = direction[o][i][j];
				if (d.first + 1 < asz && d.second + 1 < bsz && direction[d.first + 1][d.second + 1][j].first != -1){
					direction[o][i][j + 1] = direction[d.first + 1][d.second + 1][j];
				}else{
					break;
				}
			}
		}
	}
	long long int ret = 0;
	for (int i = bsz - 1; i >= 0; i--){
		for (int o = asz - 1; o >= 0; o--){
			if (direction[o][i][0].first == -1)
				continue;
			long long int u = 0, ka = o, kb = i, tmp;
			for (int j = log2lst[bsz / 2]; j >= 0; j--){
				if (direction[ka][kb][j].first != -1 && direction[ka][kb][j].second <= i + bsz / 2){
					tmp = direction[ka][kb][j].first + 1;
					kb = direction[ka][kb][j].second + 1;
					ka = tmp;
					u += 1 << j;
				}
				if (ka >= asz || kb >= bsz){
					break;
				}
			}
			ret = max(ret, u);
		}
	}
	cout << ret;
	return 0;
}

• Subtask 1: 8 / 100