Submission #1059875

#TimeUsernameProblemLanguageResultExecution timeMemory
1059875_8_8_Copy and Paste 3 (JOI22_copypaste3)C++17
20 / 100
370 ms159192 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2500 + 2,MOD = (int)1e9 + 7; struct H{ int p,mod; vector<ll> h,inv; ll binpow(ll a,ll b) { ll ret = 1,k = a; while(b) { if(b & 1) { ret *= k; ret %= mod; } k *= k; k%=mod; b /= 2; } return ret; } void init(string s) { int n = (int)s.size(); h.resize((int)s.size()); inv.resize((int)s.size()); ll x = 1; for(int i = 0;i < n;i++) { h[i] = x * 1ll * (s[i] - 'a' + 1)%mod; if(i) h[i] += h[i - 1]; if(h[i] >= mod) h[i] -= mod; inv[i] = binpow(x,mod-2); x = x * 1ll * p%mod; } } int get(int l,int r) { ll val = h[r]; if(l) { val -= h[l - 1]; } if(val < 0) val += mod; val = val * inv[l]%mod; return val; } }xx,yy; string s; ll a,b,c; int n; ll dp[N][N]; int nx[N][N]; map<pair<int,int>,vector<pair<int,int>>> f; vector<array<int,3>> x; void test() { cin >> n >> s >> a >> b >> c; yy.p = 37;yy.mod = 998244353;yy.init(s); xx.p = 167;xx.mod = (int)1e9 + 7;xx.init(s); bool sub = true; for(int i = 0;i < n;i++) { if(s[i] != 'a') { sub = false; } } ll res = n * 1ll * a; for(int i = 0;i < n;i++) { for(int j = i;j < n;j++) { int ff = xx.get(i,j),tt = 0; f[{ff,tt}].push_back({i,j}); } } for(int l = 0;l < n;l++) { for(int r = 0;r < n;r++) { dp[l][r] = 1e18; } } for(auto [t,k]:f) { int it = (int)k.size() - 1; for(int j = (int)k.size() - 1;j >= 0;j--) { while(it >= 0 && k[it].first > k[j].second) { it--; } if(it == (int)k.size() - 1) { nx[k[j].first][k[j].second] = -1; } else { nx[k[j].first][k[j].second] = k[it + 1].first; } } } for(int i = 0;i < n;i++) { dp[i][i] = a; } for(int s = 1;s <= n;s++) { for(int l = 0;l + s - 1 < n;l++) { x.push_back({s,l,l + s - 1}); } } for(auto [s,l,r]:x) { dp[l][r] = min({dp[l][r],dp[l + 1][r] + a,dp[l][r - 1] + a}); int l_ = l,r_ = r; int occ = 1; int len = (r - l + 1); // cout << l << ' ' << r << ' ' << dp[l][r] << '\n'; while(l_ != -1) { // cout << l_ << "x\n"; int sz = (r_ - l + 1); ll val = (sz - occ * 1ll * len) * 1ll * a + b + occ * c + dp[l][r]; dp[l][r_] = min(dp[l][r_],val); occ++; l_ = nx[l_][r_]; r_ = l_ + len - 1; } } cout << dp[0][n-1] << '\n'; } signed main() { ios_base::sync_with_stdio(false);cin.tie(0); int t = 1; // cin >> t; while(t--) { test(); } }

Compilation message (stderr)

copypaste3.cpp: In function 'void test()':
copypaste3.cpp:58:10: warning: variable 'sub' set but not used [-Wunused-but-set-variable]
   58 |     bool sub = true;
      |          ^~~
copypaste3.cpp:64:8: warning: unused variable 'res' [-Wunused-variable]
   64 |     ll res = n * 1ll * a;
      |        ^~~
#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...