Submission #1217953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217953		jerzyk	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	914 ms	54532 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;
#define st first
#define nd second
#define pb push_back
typedef long long ll;
typedef long double ld;
const pair<ll, ll> P = pair{127LL, 313LL};
const pair<ll, ll> M = {2147483647LL, 1000000007LL};
const ll I = (1LL<<61LL);
const int N = 2500 + 7;
ll A, B, C;

string s;
pair<ll, ll> has[N], pot[N];

int nxt[N][N];
ll dp[N][N];

void Do(int n)
{
    pot[0] = pair{1LL, 1LL};
    for(int i = 1; i <= n + 2; ++i)
        pot[i] = pair{(pot[i - 1].st * P.st) % M.st, (pot[i - 1].nd * P.nd) % M.nd};
    for(int i = 1; i <= n; ++i)
        has[i] = pair{(has[i - 1].st + (ll)(s[i] - 'a') * pot[i].st) % M.st, (has[i - 1].nd + (ll)(s[i] - 'a') * pot[i].nd) % M.nd};
}

pair<ll, ll> Get(int l, int r, int n)
{
    ll a = has[r].st - has[l - 1].st;
    a += M.st; a %= M.st;
    a = (a * pot[n - l].st) % M.st;

    ll b = has[r].nd - has[l - 1].nd;
    b += M.nd; b %= M.nd;
    b = (b * pot[n - l].nd) % M.nd;
    return pair{a, b};
}

void Calc(int n, int d)
{
    map<pair<ll, ll>, int> lst;
    for(int i = n - d + 1; i >= 1; --i)
    {
        if(i + (2 * d) - 1 <= n)
            lst[Get(i + d, i + (2 * d) - 1, n)] = i + d;
        pair<ll, ll> a = Get(i, i + d - 1, n);
        if(lst.find(a) == lst.end())
            lst[a] = n + 1;
        nxt[i][d] = lst[a];
    }
}

void Solve()
{
    int n;
    cin >> n;
    cin >> s; s = '#' + s;
    cin >> A >> B >> C;
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            dp[i][j] = (ll)(j - i + 1) * A;
    Do(n);
    for(int i = 1; i < n; ++i)
        Calc(n, i);
    for(int d = 1; d <= n; ++d)
        for(int i = 1; i <= n - d + 1; ++i)
        {
            int j = i + d - 1;
            dp[i][j] = min(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]) + A);
            //cout << i << " " << j << " " << dp[i][j] << " " << nxt[i][d] << "\n";
            if(d == n) continue;
            ll a = dp[i][j] + B + C;
            int p = i;
            while(p <= n)
            {
                dp[i][p + d - 1] = min(dp[i][p + d - 1], a);
                a += C + (ll)(nxt[p][d] - p - d) * A;
                p = nxt[p][d];
            }
        }
    cout << dp[1][n] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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