Submission #584445

#	Time	Username	Problem	Language	Result	Execution time	Memory
584445		amunduzbaev	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	0 / 85	66 ms	212 KiB

necklace

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
//~ #define int ll

const int N = 3005;
int is[N][N], d[N][N], u[N][N], ur[N][N], dl[N][N];

ar<int, 3> solve(string a, string b){
	ar<int, 3> res {};
	int n = a.size(), m = b.size();
	//~ if(n > m) swap(n, m), swap(a, b);
	
	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 s = string(a.begin() + i - k, a.begin() + i);
				string t = string(b.begin() + j, b.begin() + j + k);
				if(s == t) mx = k;
			}
			
			for(int k=0;k<=min(j, n - i);k++){
				string s = string(a.begin() + i, a.begin() + i + k);
				string t = string(b.begin() + j - k, b.begin() + j);
				if(s == t) res = max(res, {mx + k, i - mx, j - k});
			}
		}
	}
	
	return res;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	string a, b; cin>>a>>b;
	ar<int, 3> res {};
	res = solve(a, b);
	reverse(b.begin(), b.end());
	res = max(res, solve(a, b));
	
	assert(res[0]);
	cout<<res[0]<<"\n";
	cout<<res[1]<<" "<<res[2]<<"\n";
}

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