제출 #1190098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190098		crafticat	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	85 / 85	495 ms	71136 KiB

necklace

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define R0F(i, n) for (int i = n - 1; i >= 0;i--)
#define FOR(i, j, n) for(int i = j; i < n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;

constexpr int INF = 1e9;

V<vi> computeDp(string s1, string s2) {
    V<vi> dp(s1.size(), vi(s2.size()));

    R0F(i, s1.size()) {
        R0F(j, s2.size()) {
            if (i == 3 and j == 4) {
                int stop = 25;
            }
            if (s1[i] == s2[j])
                dp[i][j] = (i + 1 >= s1.size() or j + 1 >= s2.size()) ? 1 : dp[i + 1][j + 1] + 1;
            else
                dp[i][j] = 0;
        }
    }

    return dp;
}

pair<int, pair<int,int>> solve(string s1, string s2) {
    V<vi> dp1 = computeDp(s1, s2);
    V<vi> dp2(s1.size(), vi(s2.size()));

    F0R(i, s1.size()) {
        deque<pair<int, int>> deq;

        F0R(j, s2.size()) {
            if (deq.empty() or deq.back().first < dp1[i][j] + j)
                deq.push_back({dp1[i][j] + j, j});
            while (!deq.empty() and deq.front().first < j)
                deq.pop_front();

            dp2[i][j] = j - deq.front().second;
        }
    }

    pair<int, pair<int,int>> ans = {0, {0, 0}};

    F0R(j, s2.size()) {
        deque<pair<int, int>> deq; // to, from

        F0R(i, s1.size()) {
            if (deq.empty() or deq.back().first < dp1[i][j] + i)
                deq.push_back({dp1[i][j] + i, i});

            while (!deq.empty() and deq.front().first < i)
                deq.pop_front();

            ans = max(ans, {i - deq.front().second + dp2[i][j], {deq.front().second, j - (dp2[i][j])}});

        }

    }
    return ans;
}

int main() {
    string s1, s2; cin >> s1 >> s2;

    auto [v1, f1] = solve(s1, s2); reverse(s2.begin(), s2.end());
    auto [v2, f2] = solve(s1, s2);
    if (v2 > v1) {
        v1 = v2;
        f1 = f2;
        f1.second = s2.size() - f1.second - v1; // Inverse
    }

    cout << v1 << endl;
    cout << f1.first << " " << f1.second << endl;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40