#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const ll mod = 1000000000100011;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const ll P = 59;
ll convert(char c){
return (c-'a') + 1;
}
void solve(){
int n;
cin >> n;
string s;
cin >> s;
ll a , b , c;
cin >> a >> b >> c;
ll dp[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dp[i][j] = 1e18;
}
}
ll hash_val[n][n];
for(int l = 1; l <= n; l++)
{
hash_val[l][l] = (s[l] - 'a' + 1);
for(int r = l+1; r <= n; r++)
{
hash_val[l][r] = (hash_val[l][r-1] * P + (s[r] - 'a' + 1)) % mod;
}
}
int next[n][n];
memset(next,-1,sizeof next);
for(int len = 0; len < n; len++){
vector<pair<int,int>> v;
for(int i = 0; i + len < n; i++){
v.pb(mp(hash_val[i][i+len],i));
}
sort(all(v));
while(v.size()){
int hash = v.back().vf;
for(int i = v.size()-1; i >= 0 && v[i].vf == hash; i--){
while(v.size() > i + 2 && v[v.size()-2].vs > v[i].vs + len)
v.pop_back();
if(v.back().vs > v[i].vs + len)
next[v[i].vs][v[i].vs+len] = v.back().vs;
}
while(v.size() && v.back().vf == hash)
v.pop_back();
}
}
for(int len = 0; len < n; len++){
for(int i = 0; i + len < n; i++){
int j = i + len;
dp[i][j] = min(dp[i][j],(len+1LL)*a);
if(len > 0){
dp[i][j] = min(dp[i][j] , min(dp[i+1][j] , dp[i][j-1]) + a);
}
ll val = dp[i][j] + b;
val += c;
int x = i , y = j;
while(next[x][y] != -1){
int pos = next[x][y];
val += c;
val += (pos - (y + 1LL))*a;
dp[i][pos + len] = min(dp[i][pos+len],val);
x = pos;
y = pos + len;
}
}
}
cout << dp[0][n-1] << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
Compilation message
copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:60:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
60 | while(v.size() > i + 2 && v[v.size()-2].vs > v[i].vs + len)
| ~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
