Submission #554903

#TimeUsernameProblemLanguageResultExecution timeMemory
554903UncoolAnonCopy and Paste 3 (JOI22_copypaste3)C++17
20 / 100
1555 ms740 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int inf=(1LL<<60); int n,a,b,c; string s; vector<int> z(string s) { int n = (int) s.length(); vector<int> z(n); for (int i = 1, l = 0, r = 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; } int solve(string s){ int n=s.size(); vector<int> p=z(s),dp(n,inf); vector<vector<int>> A(n+1); set<int> cur; for(int i=1;i<n;i++){ if(p[i]==0) continue; A[p[i]].push_back(i); cur.insert(i); } //for(int&x:p) cout << x << " " ; cout << endl << s << endl ; // return 0 ; dp[0]=a; for(int i=0;i<n;i++){ if(i) dp[i]=min(dp[i],dp[i-1]+a); int mx=1,last=i; while(1){ auto it = cur.lower_bound(last+1); if(it==cur.end()) break; last=*it+i; mx++; dp[last]=min(dp[last],dp[i]+b+c*mx+a*(last-i-(mx-1)*(i+1))); } for(int x:A[i+1]) cur.erase(x); } return dp.back(); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); cin>>n>>s>>a>>b>>c; reverse(s.begin(),s.end()); int answer=inf; for(int i=0;i<n;i++){ string ns; for(int j=i;j<n;j++)ns+=s[j]; answer=min(answer,solve(ns)+a*i); } cout << answer; }
#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...