oj.uz

Submission #584492

# Submission time Handle Problem Language Result Execution time Memory
584492 2022-06-27T13:08:17 Z amunduzbaev Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 442 ms 177228 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 {};
	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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 177000 KB Output is correct
2 Correct 80 ms 177016 KB Output is correct
3 Correct 86 ms 176908 KB Output is correct
4 Correct 81 ms 177000 KB Output is correct
5 Correct 83 ms 176936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 177000 KB Output is correct
2 Correct 80 ms 177016 KB Output is correct
3 Correct 86 ms 176908 KB Output is correct
4 Correct 81 ms 177000 KB Output is correct
5 Correct 83 ms 176936 KB Output is correct
6 Correct 89 ms 177004 KB Output is correct
7 Correct 85 ms 177016 KB Output is correct
8 Correct 88 ms 176972 KB Output is correct
9 Correct 85 ms 177008 KB Output is correct
10 Correct 90 ms 176908 KB Output is correct
11 Correct 87 ms 177228 KB Output is correct
12 Correct 84 ms 176984 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 177000 KB Output is correct
2 Correct 80 ms 177016 KB Output is correct
3 Correct 86 ms 176908 KB Output is correct
4 Correct 81 ms 177000 KB Output is correct
5 Correct 83 ms 176936 KB Output is correct
6 Correct 89 ms 177004 KB Output is correct
7 Correct 85 ms 177016 KB Output is correct
8 Correct 88 ms 176972 KB Output is correct
9 Correct 85 ms 177008 KB Output is correct
10 Correct 90 ms 176908 KB Output is correct
11 Correct 87 ms 177228 KB Output is correct
12 Correct 84 ms 176984 KB Output is correct
13 Correct 414 ms 177004 KB Output is correct
14 Correct 375 ms 177100 KB Output is correct
15 Correct 442 ms 177028 KB Output is correct
16 Correct 387 ms 177032 KB Output is correct
17 Correct 350 ms 177028 KB Output is correct
18 Correct 373 ms 177024 KB Output is correct
19 Correct 386 ms 177024 KB Output is correct
20 Correct 394 ms 177024 KB Output is correct
21 Correct 416 ms 177024 KB Output is correct