Submission #584520

#	Time	Username	Problem	Language	Result	Execution time	Memory
584520		amunduzbaev	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	555 ms	440 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];
int pref[N], suff[N];

ar<int, 3> solve(string a, string b){
	//~ memset(is, 0, sizeof is);
	//~ memset(u, 0, sizeof u);
	//~ memset(d, 0, sizeof d);
	ar<int, 3> res {};
	int n = a.size(), m = b.size();
	//~ cout<<a<<"\n"<<b<<"\n";
	deque<ar<int, 2>> ns(n);
	
	for(int j=0;j<m;j++){
		ns.push_front({0, 0});
		for(int i=0;i<=n;i++){
			if(ns[i][1]) ns[i][1]--, ns[i][0]++;
			else ns[i][0] = 0;
			if(a[i] == b[j] && ns[i][1] == 0){
				for(int k=0;i + k < n && j + k < m && a[i + k] == b[j + k]; k++){
					ns[i][1]++;
				}
			}
		}
		
		//~ for(int i=0;i<=n;i++){
			//~ d[i][j] = ns[i][1];
			//~ u[i][j] = ns[i][0];
		//~ }
		
		memset(pref, 0, sizeof pref);
		memset(suff, 0, sizeof suff);
		for(int i=0;i<=n;i++){
			pref[i - ns[i][0]] = max(pref[i - ns[i][0]], ns[i][0]);
			if(ns[i][1]){
				suff[i + ns[i][1] - 1] = max(suff[i + ns[i][1] - 1], ns[i][1]);
			}
		}
		for(int i=1;i<=n;i++){
			pref[i] = max(pref[i], pref[i-1] - 1);
		}
		
		for(int i=n-1;~i;i--){
			suff[i] = max(suff[i], suff[i+1] - 1);
		}
		
		//~ for(int i=0;i<=n;i++){
			//~ cout<<pref[i]<<" ";
		//~ } cout<<"\n";
		//~ for(int i=0;i<=n;i++){
			//~ cout<<suff[i]<<" ";
		//~ } cout<<"\n\n";
		
		for(int i=0;i<n;i++){
			res = max(res, {pref[i + 1] + suff[i], i - suff[i] + 1, j - pref[i + 1]});
		}
		
		ns.pop_back();
	}
	
	//~ for(int i=0;i<=n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout<<d[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	//~ for(int i=0;i<=n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout<<u[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ if(a[i] == b[j]){
				//~ is[i][j] = d[i][j] = u[i][j] = 1;
			//~ }
		//~ }
	//~ }
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ if(i && j && is[i][j]) u[i][j] += u[i-1][j-1];
			//~ res = max(res, {u[i][j], i - u[i][j] + 1, j - u[i][j] + 1});
		//~ }
	//~ }
	
	//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
	//~ for(int i=n-1;~i;i--){
		//~ for(int j=m-1;~j;j--){
			//~ if(is[i][j]) d[i][j] += d[i+1][j+1];
		//~ }
	//~ }
	
	//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout<<is[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ if(!is[i][j]) continue;
			//~ assert(j + 1 >= u[i][j]);
			//~ ur[i][j - u[i][j] + 1] = max(ur[i][j - u[i][j] + 1], u[i][j]);
			//~ dl[i][j + d[i][j] - 1] = max(dl[i][j + d[i][j] - 1], d[i][j]);
		//~ }
		
		//~ for(int j=1;j<m;j++){
			//~ ur[i][j] = max(ur[i][j], ur[i][j-1] - 1);
		//~ }
		//~ for(int j=m-1;~j;j--){
			//~ dl[i][j] = max(dl[i][j], dl[i][j+1] - 1);
		//~ }
	//~ }
	
	//~ for(int i=0;i+1<n;i++){
		//~ for(int j=1;j<m;j++){
			//~ res = max(res, {ur[i][j] + dl[i+1][j-1], i - ur[i][j] + 1, j - dl[i+1][j-1]});
		//~ }
	//~ }
	
	return res;
}

/*

qhagio
cqyqkzb

mzmxnzw
xuefnx

*/

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 {};
	tt = solve(a, b);
	tt[2] = (int)b.size() - tt[2] - tt[0];
	
	res = max(res, tt);
	
	if(!res[0]){
		cout<<0<<"\n";
		return 0;
	}
	//~ assert(res[0]);
	cout<<res[0]<<"\n";
	cout<<res[1]<<" "<<res[2]<<"\n";
}

• Subtask 1: 15 / 15