/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
#include <windows.h>
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
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;
}
Compilation message
copypaste3.cpp:10:10: fatal error: windows.h: No such file or directory
10 | #include <windows.h>
| ^~~~~~~~~~~
compilation terminated.
