Submission #1271085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271085		tvgk	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	551 ms	550516 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;
const ll inf = 1e18;

struct node
{
    int child[30];
};

vector<node> tree;
int n, nxt[mxN], val[mxN], mp[mxN * mxN];
string s;
ll add, cop, paste, dp[mxN][mxN];

void Walk(int& j, int lst)
{
    if (tree[j].child[lst])
        j = tree[j].child[lst];
    else
    {
        j = tree[j].child[lst] = tree.size();
        tree.resize(j + 1);
    }
}

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;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            dp[i][j] = inf;
    }

    tree.resize(1);
    s = '-' + s;
    for (int i = 1; i <= n; i++)
    {
        for (int j = n - i + 1; j >= 1; j--)
        {
            Walk(val[j], s[j + i - 1] - 'a');
            if (j + i + i - 1 <= n)
                mp[val[j + i]] = j + i;

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

            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: 38 / 38