Submission #874883

#TimeUsernameProblemLanguageResultExecution timeMemory
874883NK_Copy and Paste 3 (JOI22_copypaste3)C++17
62 / 100
3066 ms366328 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define f first #define s second #define mp make_pair #define sz(x) int(x.size()) using pi = pair<int, int>; using ll = long long; template<class T> using V = vector<T>; using vi = V<int>; using vl = V<ll>; using vpi = V<pi>; using str = string; const int MOD = 1e9 + 7; const ll b1 = 2003; const ll b2 = 1009; const ll INFL = ll(1e18); const int LG = 18; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; str S; cin >> S; ll a, b, c; cin >> a >> b >> c; V<vl> dp(N, vl(N, INFL)); V<vi> nxt(N, vi(N, -1)); for(int l = 0; l < N; l++) for(int r = l; r < N; r++) dp[l][r] = (r - l + 1) * a; map<ll, int> C; V<V<vi>> H(N); for(int l = 0; l < N; l++) { ll h1 = 0, h2 = 0; for(int w = 0; l + w < N; w++) { h1 = (b1 * h1 + S[l + w]) % MOD; h2 = (b2 * h2 + S[l + w]) % MOD; // cout << l << " " << w << " " << h << endl; ll h = MOD * h1 + h2; if (C.find(h) == C.end()) C[h] = sz(H[w]), H[w].pb({}); H[w][C[h]].pb(l); } } for(int w = 0; w < N; w++) { // cout << w << endl; for(auto& v : H[w]) { // for(auto& x : v) cout << x << " "; // cout << endl; v.pb(-1); int j = sz(v) - 1; for(int i = sz(v) - 2; i >= 0; i--) { while(j - 1 >= 0 && (v[i] + w) < v[j - 1]) j--; nxt[v[i]][v[i] + w] = v[j]; } } // cout << endl; } // for(int l = 0; l < N; l++) for(int r = l; r < N; r++) { // if (nxt[l][r] >= MOD) nxt[l][r] = -1; // // cout << l << " " << r << " " << nxt[l][r] << endl; // } for(int w = 0; w < N; w++) { for(int l = 0; l + w < N; l++) { int r = l + w; if (r-1 >= 0) dp[l][r] = min(dp[l][r], dp[l][r-1] + a); if (l+1 < N) dp[l][r] = min(dp[l][r], dp[l+1][r] + a); // cout << l << " " << r << " " << dp[l][r] << endl; int L = l; ll amt = 1; while(nxt[L][L + w] != -1) { L = nxt[L][L + w], amt++; ll left = (L + w - l + 1) - (l + w - l + 1) * amt; dp[l][L + w] = min(dp[l][L + w], dp[l][r] + b + c * amt + left * a); // cout << l << " " << l + w << " " << L << " " << L + w << " => " << dp[l][L + w] << endl; } } } cout << dp[0][N-1] << nl; exit(0-0); }
#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...