This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//bruhed
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, A, B, C;
string s;
cin >> n >> s >> A >> B >> C;
s = '.' + s;
int id[n+1][n+2], cost[n+1][n+2];
for (int i=0;i<=n;i++) for (int j=1;j<=n+1;j++) id[i][j] = -1, cost[i][j] = INF;
for (int i=1;i<=n;i++) cost[1][i] = A;
for (int sz=1;sz<=n;sz++) {
// cout << sz << endl;
if (sz!=1) {
for (int i=1;i<=n-sz+1;i++) {
cost[sz][i] = min(cost[sz-1][i] + A, cost[sz][i]);
cost[sz][i] = min(cost[sz-1][i+1] + A, cost[sz][i]);
// cout << cost[sz][i] << " ";
}
}
// cout << endl;
vector<pair<char,int>> v = {{' ', -1}};
for (int i=1;i<=n-sz+1;i++) v.push_back({s[i], id[sz-1][i+1]});
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
// for (auto [x, y]:v) cout << x << " " << y << endl;
int m = v.size() - 1;
vector<int> mem[m+1];
for (int i=1;i<=n-sz+1;i++) {
id[sz][i] = lower_bound(v.begin(), v.end(), make_pair(s[i], id[sz-1][i+1])) - v.begin();
mem[id[sz][i]].push_back(i);
}
for (int i=1;i<=m;i++) mem[i].push_back(INF);
for (int i=1;i<=m;i++) {
for (int J=0;J<(int)mem[i].size()-1;J++) {
int j = mem[i][J];
for (int cnt = 2; ;cnt++) {
if (J+cnt-1 > (int)mem[i].size()-1) break;
int nxt = max(*lower_bound(mem[i].begin(), mem[i].end(), j + (cnt-1)*sz), mem[i][J+cnt-1]);
if (nxt==INF) break;
int SZ = nxt + sz - j;
int val = (SZ - cnt*sz)*A + C*cnt + cost[sz][j] + B;
// if (SZ == 3 && j == 4) cout << "test " << cnt << " " << val << endl;
cost[SZ][j] = min(val, cost[SZ][j]);
}
}
}
}
cout << cost[n][1] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |