Submission #501540

#	Time	Username	Problem	Language	Result	Execution time	Memory
501540		Arnch	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	436 ms	165708 KiB

necklace

// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long long ld;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 3e3 + 10, mod = 1e9 + 7, pr = 1000696969;

string s, t;
string st[2][N];

int n, m;
int f[2][N][N * 2];

void calc_f(int x, int y) {
	f[x][y][0] = 0;
	int k = 0;
	
	for(int i = 1; i < Sz(st[x][y]); i++) {
		while(k && st[x][y][k] != st[x][y][i]) 
			k = f[x][y][k - 1];

		k += (st[x][y][k] == st[x][y][i]);
		f[x][y][i] = k;
	}
}


int main() {
    fast_io;
	
	cin >>s >>t;
	n = Sz(s), m = Sz(t);
	
	st[0][n] = st[1][m] = "";
	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = s[i] + st[0][i + 1];
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = t[i] + st[1][i + 1];

	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = st[0][i] + '#' + t;
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = st[1][i] + '#' + s;

	for(int i = 0; i < n; i++)
		calc_f(0, i);
	for(int i = 0; i < m; i++)
		calc_f(1, i);	

		
	int ans = 0, pos1 = 0, pos2 = 0;
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			int val = f[1][i][j + m - i + 1];
			if(j < n - 1 && i > 0 && n - j + i - 1 < m + n - j)
				val += f[0][j + 1][n - j + i - 1];


			ans = max(ans, val);
			if(ans == val) {
				pos1 = j - f[1][i][j + m - i + 1] + 1;
				pos2 = i - f[0][j + 1][n - j + i - 1];
			}
		}
	}

	reverse(all(t));


	st[0][n] = st[1][m] = "";
	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = s[i] + st[0][i + 1];
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = t[i] + st[1][i + 1];

	for(int i = n - 1; i >= 0; i--) 
		st[0][i] = st[0][i] + '#' + t;
	for(int i = m - 1; i >= 0; i--)
		st[1][i] = st[1][i] + '#' + s;

	for(int i = 0; i < n; i++)
		calc_f(0, i);
	for(int i = 0; i < m; i++)
		calc_f(1, i);	

		
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			int val = f[1][i][j + m - i + 1];
			if(j < n - 1 && i > 0 && n - j + i - 1 < m + n - j)
				val += f[0][j + 1][n - j + i - 1];


			ans = max(ans, val);
			if(ans == val) {
				pos1 = j - f[1][i][j + m - i + 1] + 1;
				pos2 = (m - (i - f[0][j + 1][n - j + i - 1])) - val;
			}
		}
	}

	cout<<ans <<endl <<pos1 <<" " <<pos2 <<endl;

    return 0;
}

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