제출 #1200512

#제출 시각아이디문제언어결과실행 시간메모리
1200512tfgsRound words (IZhO13_rowords)C++17
100 / 100
75 ms43452 KiB
#ifndef LOCAL #include <bits/stdc++.h> #endif using namespace std; #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #pragma GCC target("avx2") #define int int64_t const int inf=1e18; #ifdef LOCAL #include "algo/debug.h" #else template <typename... Args> void dummy(Args&&... args){} #define ps dummy #endif #define f first #define s second template<class T> using V = vector<T>; using vi = V<int>; using vb = V<bool>; using vs = V<string>; #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define len(x) (int)((x).size()) #define rsz resize #define ins insert #define ft front() #define bk back() #define pb push_back #define eb emplace_back #define pf push_front #define lb lower_bound #define ub upper_bound #define ai2 array<int,2> #define ai3 array<int,3> #define ai4 array<int,4> #define ai5 array<int,5> template<class T> int lwb(const V<T>& a, const T& b) { return lb(all(a),b)-begin(a); } template<class T> int upb(const V<T>& a, const T& b) { return ub(all(a),b)-begin(a); } template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; } #define pct __builtin_popcountll #define ctz __builtin_ctzll #define clz __builtin_clzll constexpr int p2(int x) { return (int)1 << x; } constexpr int msk2(int x) { return (int)(1 << x) - 1; } constexpr int bits(int x) { return x == 0 ? 0 : 63-clz(x); } // floor(log2(x)) template<class T>void UNIQUE(V<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); } template<class T, class Cmp>void UNIQUE(V<T>& v, Cmp cmp) { sort(all(v), cmp); v.erase(unique(all(v)),end(v)); } template<class T,class U>void erase(T& t, const U& u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); } template<class F> struct y_combinator_result { F f; template<class T> explicit y_combinator_result(T &&f): f(std::forward<T>(f)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return f(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) yy(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } struct Bit { int n; vi a; Bit(int n) : n(n + 1), a(n + 1) {} void point_add(int i, int x) { i++; for (; i < n; i += i & -i) { a[i] += x; } } int prefix_sum(int r) { int res = 0; for (; r > 0; r -= r & -r) { res += a[r]; } return res; } }; void solve() { string s, t; cin >> s >> t; t = t + t; int n = len(s); int m = len(t); int ans = 0; auto work = [&]() { vector i_h(n + 1, vi(m + 1)); auto i_v = i_h; for (int j = 0; j <= m; j++) i_h[0][j] = j; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i - 1] == t[j - 1]) { i_h[i][j] = i_v[i][j - 1]; i_v[i][j] = i_h[i - 1][j]; } else { i_h[i][j] = max(i_v[i][j - 1], i_h[i - 1][j]); i_v[i][j] = min(i_v[i][j - 1], i_h[i - 1][j]); } } } Bit i_h_vals(m / 2 + 1); for (int i = 1; i <= m / 2; i++) { i_h_vals.point_add(i_h[n][i], 1); } for (int i = 1; i <= m / 2; i++) { ckmax(ans, i_h_vals.prefix_sum(i)); i_h_vals.point_add(i_h[n][i], -1); i_h_vals.point_add(i_h[n][i + m / 2], 1); } }; work(); reverse(all(t)); work(); cout << ans << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...