oj.uz

Submission #584434

# Submission time Handle Problem Language Result Execution time Memory
584434 2022-06-27T11:35:00 Z amunduzbaev Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 87 ms 176972 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();
	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.0 / 25.0

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

Subtask #2
0.0 / 20.0

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

Subtask #3
0.0 / 40.0

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