Submission #542792

#TimeUsernameProblemLanguageResultExecution timeMemory
542792skittles1412Necklace (Subtask 1-3) (BOI19_necklace1)C++17
85 / 85
445 ms106284 KiB
#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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...