Submission #1370408

#TimeUsernameProblemLanguageResultExecution timeMemory
1370408pirmyratgCopy and Paste 3 (JOI22_copypaste3)C++20
62 / 100
427 ms49724 KiB
#include "bits/stdc++.h"

using namespace std;

#define int long long

const int N = 2507;
const int md = 1e9 + 181;
const int base = 47;
const int INF = 1e18;

int n, add, cop, paste;
int dp[N][N], hsh[N], pw[N], nxt[N];
string s;
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s >> add >> cop >> paste;
    s = " " + s;
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = (pw[i - 1] * base) % md;
        hsh[i] = (hsh[i - 1] * base + (s[i] - 'a' + 1)) % md;
        for (int j = 1; j <= n; j++) 
        	dp[i][j] = INF;
    }
    auto get_hash = [&](int l, int len) {
        return (hsh[l + len - 1] - hsh[l - 1] * pw[len] % md + md) % md;
    };
    for (int i = 1; i <= n; i++) {
        map<int, int> mp;
        for (int j = n - i + 1; j >= 1; j--) {
            if (j + i + i - 1 <= n) 
            	mp[get_hash(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_hash(j, i)];
            int cur_pos = j;
            int cost = dp[j][i] + cop + paste;
            while (nxt[cur_pos]) {
                cost += paste + add * (nxt[cur_pos] - cur_pos - i);
                cur_pos = nxt[cur_pos];
                dp[j][cur_pos + i - j] = min(dp[j][cur_pos + i - j], cost);
            }
        }
    }
    cout << dp[1][n] << "\n";
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...