Submission #584434

#	Time	Username	Problem	Language	Result	Execution time	Memory
584434		amunduzbaev	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	87 ms	176972 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();
	if(n > m) swap(n, m);
	
	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++){
			//~ cout<<is[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	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});
		}
	}
	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];
		}
	}
	
	//~ 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(!is[i][j]) continue;
			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<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;
}

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