Submission #1190033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190033		crafticat	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	45 / 85	1598 ms	70980 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()) {
        F0R(j, s2.size()) {
            F0R(k, dp1[i][j] + 1) {
                if (j + k >= s2.size()) continue;
                dp2[i][j + k] = max(dp2[i][j + k], k);
            }
        }
    }

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

    F0R(i, s1.size()) {
        F0R(j, s2.size()) {
            pair<int, int> best = {dp1[i][j],0};
            F0R(k, dp1[i][j] + 1) {
                if (k + i >= s1.size()) continue;
                best = max(best, {k + dp2[k + i][j], dp2[k + i][j]});
            }

            ans = max(ans, {best.first, {i, j - best.second}});
        }
    }
    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: 0 / 40