Submission #584488

#	Time	Username	Problem	Language	Result	Execution time	Memory
584488		amunduzbaev	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	25 / 85	1587 ms	312 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());
	ar<int, 3> tt = solve(a, b);
	tt[2] = (int)b.size() - tt[2] - tt[0];
	//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
	//~ cout<<tt[0]<<" "<<tt[1]<<" "<<tt[2]<<"\n";
	
	res = max(res, tt);
	
	//~ assert(res[0]);
	if(!res[0]){
		cout<<0<<"\n";
		return 0;
	}
	cout<<res[0]<<"\n";
	cout<<res[1]<<" "<<res[2]<<"\n";
}

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