This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize "Ofast"
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cout << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cout << #arr; FR(_i, n) cout << ' ' << arr[_i]; cout << endl;}
const int MOD = 1e9 + 7;
const int X = 30;
const int MN = 2505;
int n;
string str;
int aCost, bCost, cCost;
ll pws[MN], hashes[MN];
ll dp[MN][MN];
int len;
vector<pll> vec;
int arr[MN];
void proc(int l, int r){
ms(arr, INF);
ll minCost = 0;
int prv = 0;
FOR(i, l, r){
int a = vec[i].sn;
FOR(j, prv, a+1) arr[j] = a;
prv = a+1;
minCost = max(minCost, dp[a][a+len]);
}
minCost = (ll) aCost*len - minCost + bCost;
FOR(i, l, r){
int a = vec[i].sn;
int pos = a;
int cur = 0;
while(arr[pos] != INF){
pos = arr[pos] + len;
cur++;
assert(pos <= n);
dp[a][pos] = max(dp[a][pos], (ll) cur*len*aCost - minCost - (ll) cur*cCost);
}
}
}
int main(){
boost();
cin >> n >> str >> aCost >> bCost >> cCost;
for(char &ch : str) ch -= 'a';
pws[0] = 1;
FR(i, n) pws[i+1] = pws[i] * X % MOD;
FR(i, n) hashes[i+1] = (hashes[i]*X + str[i]) % MOD;
for(len = 1; len <= n; len++){
int num = n-len+1;
vec.clear();
FR(i, num){
ll hash = (hashes[i+len] - hashes[i]*pws[len]) % MOD;
if(hash < 0) hash += MOD;
vec.pb({hash, i});
}
sort(ALL(vec));
int l = 0;
FOR(r, 1, num+1){
if(r == num || vec[r].fs != vec[r-1].fs){
proc(l, r);
l = r;
}
}
FR(i, num){
if(i) dp[i-1][i+len] = max(dp[i-1][i+len], dp[i][i+len]);
if(i < num-1) dp[i][i+len+1] = max(dp[i][i+len+1], dp[i][i+len]);
}
}
ll ans = (ll) n*aCost - dp[0][n];
cout << ans << '\n';
}
# | 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... |