Submission #703064

#TimeUsernameProblemLanguageResultExecution timeMemory
703064ajpianoCopy and Paste 3 (JOI22_copypaste3)C++17
30 / 100
380 ms49300 KiB
#include <bits/stdc++.h> using namespace std; const int tests = 0; #define f first #define s second typedef long long ll; typedef pair<ll,ll> pi; const ll mod = 1e9+9; ll mult = 29; ll binexp(ll num, ll p){ if(p == 0) return 1; if(p == 1) return num; ll ans = binexp(num, p/2LL); ans = ans*ans%mod; if(p&1) ans = ans*num%mod; return ans; } struct hashnum{ int sz = 0; ll num = 0; void add(char a){ num *= mult; num += (a-'a'+1); num %= mod; sz++; } void rem(char a){ num -= binexp(mult, sz-1)*(ll)(a-'a'+1); num %= mod; if(num < 0) num += mod; sz--; } }; void solve(){ int n; cin >> n; string s; cin >> s; ll a,b,c; cin >> a >> b >> c; ll dp[n+1][n+1]; //set up array for(int i = 1; i <= n; i++){ for(int j = 1; j+i-1 <= n; j++){ dp[i][j] = a*(ll)(i); } } //do dp for(int sz = 1; sz <= n; sz++){ hashnum curhash; vector<int> next(n+1, n+1); vector<ll> shash(n+1); map<ll, int> last; for(int i = 1; i <= sz; i++) curhash.add(s[i-1]); for(int l = 1; l+sz-1 <= n; l++){ if(sz != 1){ dp[sz][l] = min(dp[sz][l], a+min(dp[sz-1][l], dp[sz-1][l+1])); } //go through if(l > 1){ curhash.rem(s[l-2]); curhash.add(s[l+sz-2]); } //assign this substring hash shash[l] = curhash.num; //add the newly valid hash to the map if(l-sz > 0){ last[shash[l-sz]] = l-sz; } auto it = last.find(shash[l]); if(it != last.end()){ next[it->s] = l; } } for(int l = 1; l <= n; l++){ int r = next[l]; for(ll i = 2; r <= n; i++){ //cost = letter cost + pastes + cut + creation - extra letter count dp[r-l+sz][l] = min(dp[r-l+sz][l], a*(ll)(r-l - (i-1)*sz) + c*i + b + dp[sz][l]); r = next[r]; } } } cout << dp[n][1] << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; if(tests) cin >> t; while(t--) solve(); }
#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...