oj.uz

Submission #525802

# Submission time Handle Problem Language Result Execution time Memory
525802 2022-02-12T23:02:17 Z Yazan_Alattar Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 1 ms 332 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 = 305;
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;
	
	vector < vector <int> > dpS(n, vector <int> (m));
	vector < vector <int> > dpSP(n, vector <int> (m));
	vector < vector <int> > dpPS(n, vector <int> (m));
	
	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 < m; ++j){
			int len = dpSP[i][j];
			if(i + 1 < 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;
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -