제출 #933788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933788		boris_mihov	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	1502 ms	432420 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 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;
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;
}

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

컴파일 시 표준 에러 (stderr) 메시지

copypaste3.cpp: In function 'void input()':
copypaste3.cpp:113:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |     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: 0 / 38