Submission #1271071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271071		tvgk	Copy and Paste 3 (JOI22_copypaste3)	C++20	62 / 100	485 ms	49672 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 25e2 + 7, base = 31, MOD = 1e9 + 7;
const ll inf = 1e18;

int n, nxt[mxN];
string s;
ll add, cop, paste, dp[mxN][mxN], hsh[mxN], pw[mxN];
map<int, int> mp;

int Get(int u, int v)
{
    return (hsh[u + v - 1] - hsh[u - 1] * pw[v] % MOD + MOD) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    cin >> s;
    cin >> add >> cop >> paste;

    s = '-' + s;
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        pw[i] = pw[i - 1] * base % MOD;
        hsh[i] = (hsh[i - 1] * base + s[i] - 'a' + 1) % MOD;
        for (int j = 1; j <= n; j++)
            dp[i][j] = inf;
    }

    for (int i = 1; i <= n; i++)
    {
        mp.clear();
        for (int j = n - i + 1; j >= 1; j--)
        {
            if (j + i + i - 1 <= n)
                mp[Get(j + i, i)] = j + i;

            dp[j][i] = min({dp[j][i], dp[j][i - 1] + add, dp[j + 1][i - 1] + add});
            nxt[j] = mp[Get(j, i)];

            int tmp = j;
            ll cur = dp[j][i] + cop + paste;
            while (nxt[tmp])
            {
                cur += paste + add * (nxt[tmp] - tmp - i);
                tmp = nxt[tmp];
                dp[j][tmp + i - j] = min(dp[j][tmp + i - j], cur);
            }
        }
    }
    cout << dp[1][n];
}

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