Submission #1217937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217937		jerzyk	Copy and Paste 3 (JOI22_copypaste3)	C++20	62 / 100	866 ms	54352 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 ll P = 313LL;
const ll M = 694202137;
const ll I = (1LL<<31LL);
const int N = 2500 + 7;
ll A, B, C;

string s;
ll has[N], pot[N];

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

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

ll Get(int l, int r, int n)
{
    ll a = has[r] - has[l - 1];
    a += M; a %= M;
    a = (a * pot[n - l]) % M;
    return a;
}

void Calc(int n, int d)
{
    map<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;
        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: 0 / 38