Submission #525793

# Submission time Handle Problem Language Result Execution time Memory
525793 2022-02-12T22:46:01 Z Yazan_Alattar Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
66 ms 106292 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 3005;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

array <int, 3> solve (string s, string t){
	int n = s.size(), m = t.size();
	array <int, 3> ret;
	
	int dpS[M][M] = {0};
	int dpPS[M][M] = {0};
	int dpSP[M][M] = {0};
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			if(s[i] == t[j])
				dpS[i][j] = (i && j ? dpS[i - 1][j - 1] + 1 : 1);
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j) if(dpS[i][j]){
			dpPS[i - dpS[i][j] + 1][j] = max(dpPS[i - dpS[i][j] + 1][j], dpS[i][j]);
			dpSP[i][j - dpS[i][j] + 1] = max(dpSP[i][j - dpS[i][j] + 1], dpS[i][j]);
	}
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j){
			if(i) dpPS[i][j] = max(dpPS[i][j], dpPS[i - 1][j] - 1);
			if(j) dpSP[i][j] = max(dpSP[i][j], dpSP[i][j - 1] - 1);
	}
	
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			int len = dpSP[i][j];
			if(i < n && j) len += dpPS[i + 1][j - 1];
			if(len > ret[0]){
				ret[0] = len;
				ret[1] =  i - dpSP[i][j] + 1;
				ret[2] = j + dpSP[i][j] - len;
			}
		}
	}
	
	return ret;
}

int main()
{
	string s, t;
	cin >> s >> t;
	array <int, 3> ans = solve(s, t);
	
	reverse(all(t));
	array <int, 3> tmp = solve(s, t);
	tmp[2] = t.size() - tmp[2] - tmp[0];
	
	ans = max(ans, tmp);
	cout << ans[0] << endl << ans[1] << " " << ans[2] << endl;
	return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 106292 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 106292 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 106292 KB Output isn't correct
2 Halted 0 ms 0 KB -