Submission #1076579

#TimeUsernameProblemLanguageResultExecution timeMemory
1076579coldbr3wCandies (JOI18_candies)C++17
0 / 100
822 ms372612 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 3000; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 350; ll n,a,b,c; string s; vector<int> z_function(string s) { int n = s.length(); vector<int> z(n); int l = 0, r = 0; for (int i = 0; i < n; ++i) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z; } struct ccjv{int l,r,cnt;}; int st[N][13]; ll dp[N][N]; vector<ccjv>adj[N][N]; ll get(ll l, ll r){ ll p = 31 - __builtin_clz(r - l + 1); return max(st[l][p], st[r - (1 << p) + 1][p]); } void to_thic_cau(){ cin >> n >> s >> a >> b >> c; s = " " + s; for(ll i = 1; i <= n;i++){ for(ll j = 1; j <= n;j++) dp[i][j] = (j - i + 1) * a; } for(int i = 1; i <= n;i++){ string t; for(int j = i; j <= n;j++) t += s[j]; vector<int>z = z_function(t); int sz = (ll)t.size() - 1; for(int i = 0; i <= sz;i++) st[i][0] = z[i]; for(int j = 1; j <= 12;j++){ for(int i = 0; i + (1 << j) <= sz + 1;i++) st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]); } for(int len = 1; len <= sz;len++){ int cnt = 0, idx = -1, fir = -1; while(1){ int l = idx + 1, r = sz, pos = -1; while(l <= r){ ll mid = (l + r) / 2; if(get(idx + 1, mid) >= len) pos = mid, r = mid - 1; else l = mid + 1; } if(pos == -1) break; if(fir == -1) fir = pos; idx = pos + len - 1, cnt++; adj[fir + i][idx + i].pb({fir + i, fir + len - 1 + i, cnt}); } } } for(int len = 0; len <= n;len++){ for(ll i = 1; i + len <= n;i++){ ll j = i + len; for(auto x : adj[i][j]){ ll l = x.l, r = x.r, cnt = x.cnt; if(l == i && r == j) continue; dp[i][j] = min(dp[i][j], ((j - i + 1) - (r - l + 1) * cnt) * a + b + dp[l][r] + c * cnt); } if(i - 1 >= 0) dp[i-1][j] = min(dp[i-1][j], dp[i][j] + a); if(j + 1 <= n) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + a); } } cout << dp[1][n] << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...