Submission #1370403

#TimeUsernameProblemLanguageResultExecution timeMemory
1370403pirmyratgCopy and Paste 3 (JOI22_copypaste3)C++20
57 / 100
3095 ms168340 KiB
#include "bits/stdc++.h"

using namespace std;

#define int long long

const int N = 2507;
const int INF = 1e18;

struct node {
    int child[26];
    node() { 
    	memset(child, 0, sizeof(child)); 
    }
};
vector<node> tree;
int n, add, cop, paste;
int dp[N][N], nxt[N], val[N], mp[N * N];
string s;
void walk(int &j, int c) {
    if (tree[j].child[c]) {
        j = tree[j].child[c];
    } 
    else {
        int next_idx = tree.size();
        tree[j].child[c] = next_idx;
        tree.emplace_back();
        j = next_idx;
    }
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s >> add >> cop >> paste;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) 
        	dp[i][j] = INF;
    }
    tree.emplace_back();
    s = " " + s;
    for (int i = 1; i <= n; i++) {
        memset(mp, 0, sizeof(mp));
        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 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...