oj.uz

Submission #542792

# Submission time Handle Problem Language Result Execution time Memory
542792 2022-03-28T05:32:07 Z skittles1412 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 445 ms 106284 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

vector<vector<int>> comp(string s, string t) {
	int n = sz(s), m = sz(t);
	int g[n + 1][m + 1] {};
	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			if (s[i] == t[j]) {
				g[i][j] = g[i + 1][j + 1] + 1;
			}
		}
	}
	vector<vector<int>> ans(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		int opt[m + 1];
		memset(opt, 0x3f, sizeof(opt));
		for (int j = 0; j < m; j++) {
			int &o = opt[g[i][j] + j];
			o = min(o, j);
		}
		int o = 1e9;
		for (int j = m - 1; j >= 0; j--) {
			o = min(o, opt[j + 1]);
			ans[i][j] = max(0, j - o + 1);
		}
	}
	return ans;
}

tuple<int, int, int> solve(string s, string t) {
	int n = sz(s), m = sz(t);
	auto ca = comp(s, t), cb = comp(t, s);
	tuple<int, int, int> ans {};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int p1 = ca[i][j], p2 = ((j + 1 < m && i - 1 >= 0) ? cb[j + 1][i - 1] : 0);
			ans = max(ans, tuple<int, int, int> {p1 + p2, i - p2, j - p1 + 1});
		}
	}
	return ans;
}

void solve() {
	string s, t;
	cin >> s >> t;
	auto [x, a, b] = solve(s, t);
	reverse(begin(s), end(s));
	auto [x1, a1, b1] = solve(s, t);
	dbg(x, a, b, x1, a1, b1);
	if (x1 > x) {
		x = x1;
		a = sz(s) - a1 - x;
		b = b1;
	}
	cout << x << endl;
	cout << a << " " << b << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 2132 KB Output is correct
7 Correct 7 ms 2132 KB Output is correct
8 Correct 6 ms 1876 KB Output is correct
9 Correct 6 ms 2132 KB Output is correct
10 Correct 6 ms 2152 KB Output is correct
11 Correct 7 ms 2160 KB Output is correct
12 Correct 6 ms 2004 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 2132 KB Output is correct
7 Correct 7 ms 2132 KB Output is correct
8 Correct 6 ms 1876 KB Output is correct
9 Correct 6 ms 2132 KB Output is correct
10 Correct 6 ms 2152 KB Output is correct
11 Correct 7 ms 2160 KB Output is correct
12 Correct 6 ms 2004 KB Output is correct
13 Correct 436 ms 106284 KB Output is correct
14 Correct 427 ms 106260 KB Output is correct
15 Correct 432 ms 99936 KB Output is correct
16 Correct 429 ms 104576 KB Output is correct
17 Correct 415 ms 102508 KB Output is correct
18 Correct 437 ms 105520 KB Output is correct
19 Correct 427 ms 105208 KB Output is correct
20 Correct 411 ms 102368 KB Output is correct
21 Correct 445 ms 103472 KB Output is correct