oj.uz

답안 #584475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584475 2022-06-27T12:39:18 Z amunduzbaev Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 64 ms 176900 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){
	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 = solve(a, b);
	tt[2] = (int)b.size() - tt[1] - 1;
	//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
	//~ cout<<tt[0]<<" "<<tt[1]<<" "<<tt[2]<<"\n";
	
	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
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 176900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 176900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 176900 KB Output isn't correct
2 Halted 0 ms 0 KB -