Submission #584445

# Submission time Handle Problem Language Result Execution time Memory
584445 2022-06-27T11:51:40 Z amunduzbaev Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
66 ms 212 KB
#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";
}

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -