oj.uz

Submission #525807

# Submission time Handle Problem Language Result Execution time Memory
525807 2022-02-12T23:06:42 Z Yazan_Alattar Necklace (Subtask 1-3) (BOI19_necklace1) C++11
85 / 85
 251 ms 106396 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 = {0, 0, 0};
	
	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 < 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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 106216 KB Output is correct
2 Correct 61 ms 106188 KB Output is correct
3 Correct 63 ms 106304 KB Output is correct
4 Correct 61 ms 106252 KB Output is correct
5 Correct 62 ms 106296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 106216 KB Output is correct
2 Correct 61 ms 106188 KB Output is correct
3 Correct 63 ms 106304 KB Output is correct
4 Correct 61 ms 106252 KB Output is correct
5 Correct 62 ms 106296 KB Output is correct
6 Correct 61 ms 106184 KB Output is correct
7 Correct 64 ms 106292 KB Output is correct
8 Correct 65 ms 106236 KB Output is correct
9 Correct 75 ms 106396 KB Output is correct
10 Correct 70 ms 106256 KB Output is correct
11 Correct 64 ms 106228 KB Output is correct
12 Correct 65 ms 106292 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 106216 KB Output is correct
2 Correct 61 ms 106188 KB Output is correct
3 Correct 63 ms 106304 KB Output is correct
4 Correct 61 ms 106252 KB Output is correct
5 Correct 62 ms 106296 KB Output is correct
6 Correct 61 ms 106184 KB Output is correct
7 Correct 64 ms 106292 KB Output is correct
8 Correct 65 ms 106236 KB Output is correct
9 Correct 75 ms 106396 KB Output is correct
10 Correct 70 ms 106256 KB Output is correct
11 Correct 64 ms 106228 KB Output is correct
12 Correct 65 ms 106292 KB Output is correct
13 Correct 237 ms 106308 KB Output is correct
14 Correct 208 ms 106316 KB Output is correct
15 Correct 251 ms 106316 KB Output is correct
16 Correct 210 ms 106304 KB Output is correct
17 Correct 199 ms 106180 KB Output is correct
18 Correct 195 ms 106316 KB Output is correct
19 Correct 199 ms 106308 KB Output is correct
20 Correct 231 ms 106308 KB Output is correct
21 Correct 227 ms 106316 KB Output is correct