Submission #396443

#	Time	Username	Problem	Language	Result	Execution time	Memory
396443		KoD	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	281 ms	71012 KiB

necklace

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

template <class T>
void setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
    }   
}

template <class T>
void setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
    }   
}

std::tuple<int, int, int> solve(const std::string& S, const std::string& T) {
    const int N = (int) S.size();
    const int M = (int) T.size();
    Vec<Vec<int>> match(N + 1, Vec<int>(M + 1));
    for (int i = N - 1; i >= 0; --i) {
        for (int j = M - 1; j >= 0; --j) {
            if (S[i] == T[j]) {
                match[i][j] = match[i + 1][j + 1] + 1;
            }
        }
    }
    Vec<Vec<int>> min_j(N + 1, Vec<int>(M + 1, M + 1));
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            setmin(min_j[i][std::min(match[i][j] + j, M)], j);
        }
        for (int j = M; j > 0; --j) {
            setmin(min_j[i][j - 1], min_j[i][j]);
        }
    }
    std::tuple<int, int, int> ret(0, 0, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            const auto len = match[i][j];
            const auto j2 = min_j[i + len][j];
            setmax(ret, std::make_tuple(len + (j - j2), i, j2));
        }
    }
    return ret;
}

int main() {
    std::string S, T;
    std::cin >> S >> T;
    const auto [a1, i1, j1] = solve(S, T);
    std::reverse(T.begin(), T.end());
    const auto [a2, i2, j2] = solve(S, T);
    if (a1 >= a2) {
        std::cout << a1 << '\n';
        std::cout << i1 << ' ' << j1 << '\n';
    }
    else {
        std::cout << a2 << '\n';
        std::cout << i2 << ' ' << (((int) T.size() - j2 - 1) - a2 + 1) << '\n';
    }
    return 0;
}

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