#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2500 + 2;
struct H{
int p,mod;
vector<ll> h,inv;
ll binpow(ll a,ll b) {
ll ret = 1,k = a;
while(b) {
if(b & 1) {
ret *= k;
ret %= mod;
}
k *= k;
k%=mod;
b /= 2;
}
return ret;
}
void init(string s) {
int n = (int)s.size();
h.resize((int)s.size());
inv.resize((int)s.size());
ll x = 1;
for(int i = 0;i < n;i++) {
h[i] = x * 1ll * (s[i] - 'a' + 1)%mod;
if(i) h[i] += h[i - 1];
if(h[i] >= mod) h[i] -= mod;
inv[i] = binpow(x,mod-2);
x = x * 1ll * p%mod;
}
}
int get(int l,int r) {
ll val = h[r];
if(l) {
val -= h[l - 1];
}
if(val < 0) val += mod;
val = val * inv[l]%mod;
return val;
}
}xx,yy;
string s;
ll a,b,c,h[N],p = 167,inv[N];
map<pair<int,int>,ll> mem;
ll solve(int l,int r) {
if(r == l) {
return a;
}
pair<int,int> t = {xx.get(l,r),yy.get(l,r)};
if(mem.count(t)) {
return mem[t];
}
vector<pair<pair<int,int>,array<int,2>>> x;
int mx = (r - l + 1) / 2;
for(int i = l;i <= r;i++) {
for(int j = i;j <= min(r,i+mx-1);j++) {
pair<int,int> T = {xx.get(i,j),yy.get(i,j)};
// if(j != r) continue;
x.push_back({T,{i,j}});
}
}
sort(x.begin(),x.end());
ll res = min(solve(l,r-1) + a,(r - l + 1) * 1ll * a);
int n = (r - l + 1);
for(int i = 0;i < (int)x.size();) {
int j = i;
while(j < (int)x.size() && x[i].first == x[j].first) {
j++;
}
if(x[j - 1].second[1] != r) {
i = j;
continue;
}
int mn = -1,col = 0;
for(int k = i;k < j;k++) {
if(x[k].second[0] > mn) {
mn = x[k].second[1];
col++;
}
}
int sz = (x[i].second[1] - x[i].second[0] + 1);
// cout << l << ' ' << r << ' ' << sz << ' ' << col << '\n';
if(col == 1) {
i = j;
continue;
}
assert(sz <= n / 2);
ll val = solve(x[i].second[0],x[i].second[1]) + (n - sz * 1ll * col) * 1ll * a + (col - 1) * c + b + c;
res = min(res,val);
i = j;
}
cout << l << ' ' << r << ' ' << res << '\n';
return mem[t] = res;
}
int n;
void test() {
cin >> n >> s >> a >> b >> c;
yy.p = 37;yy.mod = 998244353;yy.init(s);
xx.p = 167;xx.mod = (int)1e9 + 7;xx.init(s);
// cout << xx.get(1,2) << ' ' << yy.get(1,2) << ' ' << xx.get(4,5) << ' ' << yy.get(4,5) << '\n';
cout << solve(0,n-1);
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
| # |
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 |
1 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
