Submission #893262

#	Time	Username	Problem	Language	Result	Execution time	Memory
893262		serifefedartar	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1301 ms	110420 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MAXN = 2550;

const ll P = 37;
const ll P2 = 31;
const ll MOD1 = 1e9 + 9;
const ll MOD2 = 998244353;

ll N, A, B, C;
string s;
ll hashes1[MAXN], hashes2[MAXN], to[MAXN][MAXN], dp[MAXN][MAXN], powP1[MAXN], powP2[MAXN];
pair<ll, ll> f(int l, int r) {
    ll h = (hashes1[r] - powP1[r-l+1] * hashes1[l - 1] % MOD1) % MOD1;
    ll h2 = (hashes2[r] - powP2[r-l+1] * hashes2[l - 1] % MOD2) % MOD2;
    if (h < 0)
        h += MOD1;
    if (h2 < 0)
        h2 += MOD2;
    return {h, h2};
}

vector<int> occ[MAXN];
map<pair<ll,ll>, deque<int>> mp;

int main() {
    fast
    cin >> N >> s >> A >> B >> C;
    s = "#" + s; 

    powP1[0] = powP2[0] = 1;
    for (int i = 1; i <= N; i++)
        powP1[i] = (powP1[i-1] * P) % MOD1;
    for (int i = 1; i <= N; i++)
        powP2[i] = (powP2[i-1] * P2) % MOD2;
    for (int i = 1; i <= N; i++)
        hashes1[i] = (hashes1[i-1] * P + (s[i] - 'a' + 1)) % MOD1;
    for (int i = 1; i <= N; i++)
        hashes2[i] = (hashes2[i-1] * P2 + (s[i] - 'a' + 1)) % MOD2;

    for (int len = 1; len <= N; len++) {
        mp.clear();
        for (int j = N-len+1; j >= 1; j--) {
            pair<ll, ll> h = f(j, j + len - 1);
            while (mp[h].size() >= 2 && mp[h][1] > j + len - 1)
                mp[h].pop_front();

            to[j][len] = (mp[h].size() == 0 ? 0 : mp[h].front());
            if (to[j][len] <= j + len - 1)
                to[j][len] = 0;

            if (to[j][len])
                occ[j].push_back(len);
            mp[h].push_back(j);
        }
    }

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

    for (int l = N; l >= 1; l--) {
        dp[l][l] = A;
        for (int r = l+1; r <= N; r++)
            dp[l][r] = min(dp[l][r], min(dp[l+1][r] + A, dp[l][r-1] + A));

        for (auto len : occ[l]) {
            int cnt = 1;
            int now = to[l][len];
            dp[l][l+len-1] = min(dp[l][l+len-1], min(dp[l][l+len-2] + A, dp[l+1][l+len-1] + A));
            ll base = dp[l][l+len-1];
            while (now != 0) {
                int total = now - l - cnt * len;
                dp[l][now + len - 1] = min(dp[l][now + len - 1], total * A + B + C * (cnt + 1) + base);
                cnt++;
                now = to[now][len];
            }
        }

        for (int r = l+1; r <= N; r++)
            dp[l][r] = min(dp[l][r], min(dp[l+1][r] + A, dp[l][r-1] + A));
    }
    cout << dp[1][N] << "\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