Submission #303063

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

necklace

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

int main(){
	cin >> a;
	a = '0' + a;
	cin >> b;
	b = '0' + b;
	fazdp(0);
	reverse(b.begin(), b.end());
	fazdp(1);
	cout << ans << endl;
	cout << ians << ' ' << jans << endl;
}

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