제출 #642594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642594		aebov	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	25 / 85	1584 ms	304 KiB

necklace

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<utility>
#define pii pair<int, int>
#define F first
#define S second
#define ll long long
#define pb push_back
using namespace std;

int n ,m ;
string s ,t;

pair<int,pii> ans(string a, string b){
	pair<int , pii > ret; n = a.size(), m = b.size();

	for(int i = 0 ; i <= n; i ++){
		for(int j = 0;j <= m; j ++){
			int mx = 0;
			for(int k = 1 ; k <= min(i, m - j) ; k ++){
				string s2 = string(a.begin() + i - k, a.begin() + i);
				string t2 = string(b.begin() + j, b.begin() + j + k);
				if(s2 == t2)mx = k;
			}

			for(int k = 0 ; k <= min (j, n - i); k ++){
				string s2 = string(a.begin() + i, a.begin() + i + k);
				string t2 = string(b.begin() + j - k, b.begin() + j);
				if(s2 == t2){
					ret = max(ret, {mx + k,{ i - mx, j - k } });
				}
			}
		}
	}
	return ret;
}
int main(){
	cin >> s >> t;

	auto ret = ans(s, t);
	reverse(t.begin(), t.end());
	auto ter = ans(s, t);
	ter.S.S = (int)t.size() - ter.S.S - ter.F;

	ret = max(ret, ter);

	if(!ret.F){
		cout << 0 << endl;
		return 0;
	}
	cout << ret.F << endl << ret.S.F << " " << ret.S.S << endl; 

}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40