Submission #303070

#	Time	Username	Problem	Language	Result	Execution time	Memory
303070		bigg	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	85 / 85	210 ms	71292 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3010;
int dpsufsuf[MAXN][MAXN], dpprefsuf[MAXN][MAXN];
char a[MAXN], b[MAXN];
int ans, ians, jans;
void fazdp(int isrev){
	int t1 = strlen(a + 1);
	int t2 = strlen(b + 1);
	
	for(int i = t1; i; i--){
		for(int j = t2; j; j--){
			if(a[i] == b[j]){
				dpsufsuf[i][j] = 1 + dpsufsuf[i+1][j+1];
				dpprefsuf[i + dpsufsuf[i][j] - 1][j] = max(dpprefsuf[i + dpsufsuf[i][j] - 1][j], dpsufsuf[i][j]);
	
			}
		}
	}
	// for(int i = t1; i ; i--){
	// 	for(int j = t2; j; j--){
	// 		if(a[i] == b[j]){
	// 				}
	// 	}
	// }
	for(int i = 1; i <= t1; i++){
		for(int j = 1; j <= t2; j++){
			int v = dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j];
			if( v > ans){
				if(!isrev) jans = j;
				else{
					int aux = j + v -1;
					jans = t2 - aux + 1;
				}
				ians = i - dpprefsuf[i-1][j + dpsufsuf[i][j]];
				ans = v;
			}
		}
	}
}

int main(){
	cin >>( a + 1);
	//a = '0' + a;
	cin >> (b + 1);
	//b = '0' + b;
	fazdp(0);
	int st = strlen(b + 1);
	//cout << b +1;
	for(int i = 1, j = st; i < j; i++, j--){
		swap(b[i], b[j]);

	}
	memset(dpsufsuf, 0 , sizeof(dpsufsuf));
	memset(dpprefsuf, 0 , sizeof(dpprefsuf));
	//cout << b + 1;	
	fazdp(1);
	cout << ans << endl;
	cout << ians -1<< ' ' << jans -1 << endl;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40