Submission #584492

#	Time	Username	Problem	Language	Result	Execution time	Memory
584492		amunduzbaev	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	442 ms	177228 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){
	memset(is, 0, sizeof is);
	memset(d, 0, sizeof d);
	memset(u, 0, sizeof u);
	memset(ur, 0, sizeof ur);
	memset(dl, 0, sizeof dl);
	ar<int, 3> res {};
	int n = a.size(), m = b.size();
	
	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);
		}
	}
	//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout<<ur[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout<<dl[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	for(int i=0;i+1<n;i++){
		for(int j=1;j<m;j++){
			//~ cout<<i<<" "<<j<<" "<<ur[i][j] + dl[i+1][j-1]<<" "<<i - ur[i][j] + 1<<" "<<j - dl[i+1][j-1]<<"\n";
			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: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40