제출 #896720

#제출 시각아이디문제언어결과실행 시간메모리
896720boxNecklace (Subtask 1-3) (BOI19_necklace1)C++17
85 / 85
264 ms600 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; } #define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__) #else #define cerr if (false) cerr #define bug(...) #endif #define ar array #define all(v) std::begin(v), std::end(v) #define sz(v) int(std::size(v)) typedef long long i64; typedef vector<int> vi; typedef pair<int, int> pi; ar<int, 3> solve(const string& S, const string& T) { int N = sz(S), M = sz(T); // vector dpL(N, vi(M)), dpR(N, vi(M)); vi rollL(M), rollR(M); vi c(N + M), cc(N + M), ii(N + M); for (int d = -(N - 1); d < M; d++) { // vector<pi> ij; for (int i = 0; i < N; i++) { int j = i + d; if (0 <= j && j < M) { ii[N + d] = i; // ij.push_back({i, j}); } } /* reverse(all(ij)); int c = 0; for (auto [i, j] : ij) { if (S.at(i) == T.at(j)) c++; else c = 0; if (c) { int x = i + c - 1, y = j + c - 1; cerr << x << ' '; // bug(i, j, x, y, c); dpL.at(x).at(j) = max(dpL.at(x).at(j), c); dpR.at(i).at(y) = max(dpR.at(i).at(y), c); } } cerr << endl; */ } /* for (int j = 0; j < M; j++) for (int i = N - 1; i > 0; i--) dpL.at(i - 1).at(j) = max(dpL.at(i - 1).at(j), dpL.at(i).at(j) - 1); for (int i = 0; i < N; i++) for (int j = M - 1; j > 0; j--) dpR.at(i).at(j - 1) = max(dpR.at(i).at(j - 1), dpR.at(i).at(j) - 1); */ ar<int, 3> best{0, 0, 0}; for (int i = N; i >= 0; i--) { if (i) { for (int j = 0; j < M; j++) { rollL.at(j)--; rollL[j] = max(rollL[j], 0); } for (int d = -(N - 1); d < M; d++) { int i_ = ii[N + d], j = ii[N + d] + d, c_ = (S[i_] == T[j] ? cc[N + d] + 1 : 0); while (0 <= j && j < M && i_ + c_ - 1 == i - 1) { rollL.at(j) = max(rollL.at(j), c_); ii[N + d]--; cc[N + d] = c_; i_ = ii[N + d], j = ii[N + d] + d, c_ = (S[i_] == T[j] ? cc[N + d] + 1 : 0); } } } fill(all(rollR), 0); if (i < N) { for (int d = -(N - 1); d < M; d++) { int j = i + d; if (0 <= j && j < M) { if (S[i] == T[j]) c[N + d]++; else c[N + d] = 0; if (c[N + d]) { int y = j + c[N + d] - 1; rollR[y] = max(rollR[y], c[N + d]); } } } } for (int j = M - 1; j > 0; j--) rollR[j - 1] = max(rollR[j - 1], rollR[j] - 1); for (int j = M; j >= 0; j--) { int L = i > 0 && j < M ? rollL.at(j) : 0; int R = j > 0 && i < N ? rollR.at(j - 1) : 0; /* if (i > 0 && j < M && rollL.at(j) != dpL.at(i - 1).at(j)) bug(i - 1, j, rollL.at(j), dpL.at(i - 1).at(j)); if (j > 0 && i < N && rollR.at(j - 1) != dpR.at(i).at(j - 1)) bug(i, j - 1, rollR.at(j - 1), dpR.at(i).at(j - 1)); */ best = max(best, {L + R, i - L, j - R}); } } bug(best[0], best[1], best[2]); return best; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); string S, T; cin >> S >> T; auto one = solve(S, T); reverse(begin(T), end(T)); auto two = solve(S, T); reverse(begin(T), end(T)); two[2] = sz(T) - two[2] - two[0]; auto best = max(one, two); cout << best[0] << '\n'; cout << best[1] << ' ' << best[2] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...