제출 #1122088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122088		hamzabc	원형 문자열 (IZhO13_rowords)	C++14	20 / 100	167 ms	22084 KiB

rowords

#include <bits/stdc++.h>


using namespace std;


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


string a, b;
vector<vector<short>> memoization;
vector<vector<short>> direction;
vector<vector<pair<short, short>>> pointerD;
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;
		if (ka + 1 < asz && kb + 1 < bsz){
			direction[ka + 1][kb + 1] = 0;
			pointerD[ka][kb].first = pointerD[ka + 1][kb + 1].first;
			pointerD[ka][kb].second = pointerD[ka + 1][kb + 1].second;
		}else{
			pointerD[ka][kb].first = ka;
			pointerD[ka][kb].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){
				if (direction[ka + 1][kb] == 2 && dp(ka + 1, kb) == memoization[ka][kb])
					direction[ka + 1][kb] = 1;
				pointerD[ka][kb].first = pointerD[ka + 1][kb].first;
				pointerD[ka][kb].second = pointerD[ka + 1][kb].second;
			}else{
				pointerD[ka][kb].first = ka;
				pointerD[ka][kb].second = kb;
			}
		}else{
			// if not anything direction is this :)
			memoization[ka][kb] = dp(ka, kb + 1);
			if (ka < asz && kb + 1 < bsz){
				pointerD[ka][kb].first = pointerD[ka][kb + 1].first;
				pointerD[ka][kb].second = pointerD[ka][kb + 1].second;
			}else{
				pointerD[ka][kb].first = ka;
				pointerD[ka][kb].second = kb;
			}
		}
	}
	while (pointerD[ka][kb].second - kb > bsz / 2){
		switch(direction[pointerD[ka][kb].first][pointerD[ka][kb].second]){
		case 0:
			pointerD[ka][kb].first--;
			pointerD[ka][kb].second--;
			break;
		case 1:
			pointerD[ka][kb].first--;
			break;
		case 2:
			pointerD[ka][kb].second--;
			break;
		}
	}
	return memoization[ka][kb];
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// auto tm = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
	cin >> a >> b;
	if (a.size() > b.size())
		swap(a, b);
	b += b;
	b.pop_back();
	asz = a.size();
	bsz = b.size();
	direction.resize(asz, vector<short>(bsz, 2));
	memoization.resize(asz, vector<short>(b.size(), -1));
	pointerD.resize(asz, vector<pair<short, short>>(bsz, { 0, 0 }));
	dp(0, 0);
	int ret = 0;
	for (int i = bsz - 1; i >= 0; i--){
		for (int o = asz - 1; o >= 0; o--){
			auto d = pointerD[o][i];
			ret = max(ret, memoization[o][i] - memoization[d.first][d.second] + (a[d.first] == b[d.second]));
		}
	}
	/////////////////////////it is reverse time
	reverse(all(a));
	for (int i = 0; i < asz; i++){
		fill(all(direction[i]), 2);
		fill(all(memoization[i]), -1);
	}
	dp(0, 0);
	for (int i = bsz - 1; i >= 0; i--){
		for (int o = asz - 1; o >= 0; o--){
			auto d = pointerD[o][i];
			ret = max(ret, memoization[o][i] - memoization[d.first][d.second] + (a[d.first] == b[d.second]));
		}
	}
	cout << ret;
	// auto tm2 = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
	// cerr endl << tm2 - tm;
	return 0;
}

• Subtask 1: 20 / 100