Submission #555774

#TimeUsernameProblemLanguageResultExecution timeMemory
555774AriaHCopy and Paste 3 (JOI22_copypaste3)C++17
62 / 100
531 ms49876 KiB
/* Im the best and i work like that */ #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(),x.end() #define Mp make_pair #define point complex #define endl '\n' #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout); #define mashtali return cout << "Hello, World!", 0; #define int ll const int N = 2510; const int LOG = 20; const ll mod = 1e9 + 21; const ll base = 124338541; const ll inf = 8e18; const double pi = acos(-1); const ld eps = 1e-18; const ld one = 1.; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } mt19937 rng(time(nullptr)); int n, par[N]; ll A, B, C, Hsh[N], P[N], dp[N][N]; /// dp -> how much we can save string s; inline ll get(ll l, ll r) { return (Hsh[r] - (Hsh[l - 1] * P[r - l + 1] % mod) + mod) % mod; } int32_t main() { fast_io; for(int i = P[0] = 1; i < N; i ++) { P[i] = P[i - 1] * base % mod; } cin >> n >> s >> A >> B >> C; s = "." + s; for(int i = 1; i <= n; i ++) { Hsh[i] = (Hsh[i - 1] * base + s[i]) % mod; } for(int len = 1; len <= n; len ++) { memset(par, -1, sizeof par); vector < pll > vec; for(int i = len; i <= n; i ++) { vec.push_back(Mp(get(i - len + 1, i), i)); } for(int i = 1; i <= n; i ++) { dp[i][i + len - 1] = max({dp[i][i + len - 1], dp[i + 1][i + len - 1], dp[i][i + len - 2]}); } sort(all(vec)); for(int i = len; i <= n; i ++) { ll cu = get(i - len + 1, i); int id = lower_bound(all(vec), Mp(cu, 1ll * i + len)) - vec.begin(); if(id < SZ(vec) && vec[id].F == cu) { par[i] = vec[id].S; } } for(int i = len; i <= n; i ++) { int nxt = par[i], cnt = 1; ll cu = dp[i - len + 1][i]; while(nxt != -1) { cnt ++; dp[i - len + 1][nxt] = max(dp[i - len + 1][nxt], cu + 1ll * len * (cnt - 1) * A - B - 1ll * cnt * C); nxt = par[nxt]; } } } cout << 1ll * n * A - dp[1][n]; return 0; } /* check corner case(n = 1?), watch for negetive index or overflow */
#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...