oj.uz

Submission #584480

# Submission time Handle Problem Language Result Execution time Memory
584480 2022-06-27T12:56:10 Z amunduzbaev Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 260 ms 177152 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[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
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 176972 KB Output is correct
2 Correct 65 ms 176948 KB Output is correct
3 Correct 63 ms 176932 KB Output is correct
4 Correct 65 ms 176976 KB Output is correct
5 Partially correct 63 ms 177008 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 176972 KB Output is correct
2 Correct 65 ms 176948 KB Output is correct
3 Correct 63 ms 176932 KB Output is correct
4 Correct 65 ms 176976 KB Output is correct
5 Partially correct 63 ms 177008 KB Output is partially correct
6 Correct 71 ms 176956 KB Output is correct
7 Partially correct 75 ms 176904 KB Output is partially correct
8 Correct 74 ms 177008 KB Output is correct
9 Partially correct 65 ms 176912 KB Output is partially correct
10 Correct 68 ms 177016 KB Output is correct
11 Partially correct 66 ms 176972 KB Output is partially correct
12 Partially correct 75 ms 176928 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 176972 KB Output is correct
2 Correct 65 ms 176948 KB Output is correct
3 Correct 63 ms 176932 KB Output is correct
4 Correct 65 ms 176976 KB Output is correct
5 Partially correct 63 ms 177008 KB Output is partially correct
6 Correct 71 ms 176956 KB Output is correct
7 Partially correct 75 ms 176904 KB Output is partially correct
8 Correct 74 ms 177008 KB Output is correct
9 Partially correct 65 ms 176912 KB Output is partially correct
10 Correct 68 ms 177016 KB Output is correct
11 Partially correct 66 ms 176972 KB Output is partially correct
12 Partially correct 75 ms 176928 KB Output is partially correct
13 Correct 247 ms 176948 KB Output is correct
14 Correct 213 ms 177036 KB Output is correct
15 Partially correct 260 ms 177036 KB Output is partially correct
16 Correct 217 ms 176972 KB Output is correct
17 Correct 207 ms 177152 KB Output is correct
18 Correct 226 ms 177040 KB Output is correct
19 Correct 213 ms 177032 KB Output is correct
20 Correct 231 ms 177036 KB Output is correct
21 Partially correct 230 ms 176984 KB Output is partially correct