Submission #932571

#	Time	Username	Problem	Language	Result	Execution time	Memory
932571		alextodoran	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1400 ms	48556 KiB

copypaste3

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 2500;

int N;
string S;
int A, B, C;

vector <int> v[N_MAX + 2];

int Z[N_MAX + 2];
ll minCost[N_MAX + 2][N_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> S >> A >> B >> C;
    S = " " + S;
    for (int l = 1; l <= N; l++) {
        for (int r = l; r <= N; r++) {
            minCost[l][r] = (ll) A * (r - l + 1);
        }
    }
    for (int l = N; l >= 1; l--) {
        Z[l] = 0;
        int pos = l;
        for (int i = l + 1; i <= N; i++) {
            if (i <= pos + Z[pos] - 1) {
                Z[i] = min(pos + Z[pos] - i, Z[l + i - pos]);
            } else {
                Z[i] = 0;
            }
            while (i + Z[i] <= N && S[i + Z[i]] == S[l + Z[i]]) {
                Z[i]++;
            }
            if (i + Z[i] > pos + Z[pos]) {
                pos = i;
            }
        }
        set <int> s;
        for (int i = l + 1; i <= N; i++) {
            if (Z[i] > 0) {
                s.insert(i);
                v[Z[i]].push_back(i);
            }
        }
        for (int r = l; r <= N; r++) {
            int len = r - l + 1;
            if (len > 1) {
                for (int i : v[len - 1]) {
                    s.erase(i);
                }
                minCost[l][r] = min({minCost[l][r], minCost[l + 1][r] + A, minCost[l][r - 1] + A});
            }
            ll cost = minCost[l][r] + B;
            int i = l;
            while (true) {
                cost += C;
                minCost[l][i + len - 1] = min(minCost[l][i + len - 1], cost);
                set <int> :: iterator it = s.lower_bound(i + len);
                if (it != s.end()) {
                    cost += (ll) ((*it - i) - len) * A;
                    i = *it;
                } else {
                    break;
                }
            }
        }
        for (int len = 1; len <= N - l; len++) {
            v[len].clear();
        }
    }
    cout << minCost[1][N] << "\n";

    return 0;
}

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