Submission #933794

#	Time	Username	Problem	Language	Result	Execution time	Memory
933794		boris_mihov	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1483 ms	452460 KiB

copypaste3

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

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

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

llong a, b, c;
int next[MAXN][MAXN];
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 len = 1 ; len <= n ; ++len)
    {
        std::map <std::pair <int,int> ,int> map;
        for (int pos = n - len + 1 ; pos >= 1 ; --pos)
        {
            int r = pos + len - 1;
            next[pos][r] = map[{getHash(pos, r), getHash2(pos, r)}];
            if (r + len - 1 <= n)
            {
                map[{getHash(r, r + len - 1), getHash2(r, r + len - 1)}] = r;
            }
        } 
    }

    for (int l = 1 ; l <= n ; ++l)
    {
        for (int r = l ; r <= n ; ++r)
        {
            int left = l;
            int len = r - l;
            do
            {
                increase[l][left + len].push_back(r);
                left = next[left][left + len];
            } while (left != 0);
        }
    }

    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;

    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     if (i % 3 == 1) assert(s[i] == 'n');
    //     if (i % 3 == 2) assert(s[i] == 'q');
    //     if (i % 3 == 0) assert(s[i] == 'v');
    // }
}

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:127:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     std::cin >> s + 1;
      |                 ~~^~~

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