Submission #549863

#TimeUsernameProblemLanguageResultExecution timeMemory
549863BalintRCopy and Paste 3 (JOI22_copypaste3)C++17
25 / 100
3036 ms8220 KiB
#include <bits/stdc++.h> using namespace std; 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 = 1005; int n; string str; int aCost, bCost, cCost; ll pws[MN], hashes[MN]; ll dp[MN][MN]; int len; vector<pll> vec; void proc(int l, int r){ vi smallVec; ll minCost = 0; FOR(i, l, r){ int a = vec[i].sn; smallVec.pb(a); minCost = max(minCost, dp[a][a+len]); } minCost = (ll) aCost*len - minCost + bCost; FR(i, n){ int pos = i; int cur = 0; while(true){ int nxt = lbv(smallVec, pos); if(nxt == SZ(smallVec)) break; pos = smallVec[nxt] + len; cur++; assert(pos <= n); dp[i][pos] = max(dp[i][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; //dbgArr(pws, n+1); //dbgArr(hashes, n+1); for(len = 1; len <= n; len++){ FR(i, n) FR(j, n) dp[i][j+1] = max(dp[i][j+1], dp[i][j]); 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; } } } ll ans = (ll) n*aCost - dp[0][n]; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...