Submission #933761

#	Time	Username	Problem	Language	Result	Execution time	Memory
933761		boris_mihov	Copy and Paste 3 (JOI22_copypaste3)	C++17	30 / 100	2148 ms	427728 KiB

copypaste3

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2500 + 10;
const int ALPHABET = 26;
const int MOD = 998244353;
const int MOD2 = 1e9 + 7;
const int INF  = 1e9;

int n;
char s[MAXN];
int letter[MAXN][ALPHABET];
int fail[MAXN];

llong a, b, c;
llong dp[MAXN][MAXN];
llong cnt[MAXN][MAXN];
llong best[MAXN][MAXN];
std::vector <int> increase[MAXN][MAXN];
llong prefixHash[MAXN];
llong prefixHash2[MAXN];
llong base[MAXN];
llong base2[MAXN];

llong getHash(int l, int r)
{
    llong res = prefixHash[r] + MOD - ((prefixHash[l - 1] * base[r - l + 1]) % MOD);
    if (res >= MOD) res -= MOD;
    return res;
}

llong getHash2(int l, int r)
{
    llong res = prefixHash2[r] + MOD2 - ((prefixHash2[l - 1] * base2[r - l + 1]) % MOD2);
    if (res >= MOD2) res -= MOD2;
    return res;
}

void solve()
{
    base[0] = 1;
    base2[0] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        base[i] = (base[i - 1] * 27) % MOD;
        base2[i] = (base2[i - 1] * 27) % MOD2;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        prefixHash[i] = prefixHash[i - 1] * 27;
        prefixHash[i] += s[i] - 'a' + 1;
        prefixHash[i] %= MOD;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        prefixHash2[i] = prefixHash2[i - 1] * 27;
        prefixHash2[i] += s[i] - 'a' + 1;
        prefixHash2[i] %= MOD2;
    }

    for (int l = 1 ; l <= n ; ++l)
    {
        std::vector <int> v;
        for (int r = l ; r <= n ; ++r)
        {
            if (s[l] == s[r])
            {
                // std::cout << "add: " << l << ' ' << r << '\n';
                v.push_back(r);
                increase[l][r].push_back(l);
            }
        }

        fail[1] = 0;
        for (int c = 0 ; c < ALPHABET ; ++c)
        {
            letter[1][c] = 0;
        }

        std::string curr; curr += s[l];
        for (int r = l + 1 ; r <= n ; ++r)
        {
            curr += s[r];
            fail[r - l + 1] = fail[r - l];
            while (fail[r - l + 1] > 0 && s[l + fail[r - l + 1]] != s[r])
            {
                fail[r - l + 1] = fail[fail[r - l + 1] - 1]; 
            }

            if (s[l + fail[r - l + 1] + 1] == s[r])
            {
                fail[r - l + 1]++;
            }

            for (int c = 0 ; c < ALPHABET ; ++c)
            {
                if (s[l + letter[r - l][c]] == char('a' + c))
                {
                    letter[r - l + 1][c] = letter[r - l][c] + 1;
                } else
                {
                    if (letter[r - l][c] == 0)
                    {
                        letter[r - l + 1][c] = 0;
                    } else
                    {
                        letter[r - l + 1][c] = letter[letter[r - l][c] - 1][c];
                    }
                }
            }
            
            int last = l - 1;
            std::vector <int> newV;
            for (const int &left : v)
            {
                int len = r - l;
                int idx = left + r - l;
                int newLeft = left;

                while (len > 0 && (newLeft <= last || s[l + idx - newLeft] != s[idx]))
                {
                    len = letter[len][s[idx] - 'a'];
                    newLeft = idx - len;
                }

                // std::cout << "try: " << left << ' ' << newLeft << ' ' << idx << ' ' << last << " = " << getHash(newLeft, newLeft + r - l) << ' ' << getHash(l, r) << '\n';
                if (newLeft > last && newLeft + r - l <= n && getHash(newLeft, newLeft + r - l) == getHash(l, r) && getHash2(newLeft, newLeft + r - l) == getHash2(l, r))
                {
                    newV.push_back(newLeft);
                    last = newLeft + r - l;
                }

            }

            // std::cout << "subarray: " << curr << '\n';
            // std::cout << "at\n";

            // for (const int &left : newV)
            // {
            //     std::cout << left << ' ' << left + r - l << '\n';
            // }

            v = newV;
            for (const int &left : v)
            {
                increase[l][left + r - l].push_back(r);
            }
        }
    }

    for (int len = 1 ; len <= n ; ++len)
    {
        for (int l = 1 ; l + len - 1 <= n ; ++l)
        {
            int r = l + len - 1;
            best[l][r] = best[l][r - 1];
            for (const int &idx : increase[l][r])
            {
                cnt[l][idx]++;
                if (cnt[l][idx] > 1)
                {
                    best[l][r] = std::max(best[l][r], cnt[l][idx] * (idx - l + 1) * a - b - c * cnt[l][idx] - dp[l][idx]);
                }
            }

            dp[l][r] = a * (r - l + 1) - best[l][r];
            if (len > 1)
            {
                dp[l][r] = std::min(dp[l][r], dp[l + 1][r] + a);
                dp[l][r] = std::min(dp[l][r], dp[l][r - 1] + a);
            }
        }
    }

    std::cout << dp[1][n] << '\n';
}

void input()
{
    std::cin >> n;
    std::cin >> s + 1;
    std::cin >> a >> b >> c;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'void input()':
copypaste3.cpp:187:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  187 |     std::cin >> s + 1;
      |                 ~~^~~

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38