Submission #673657

#TimeUsernameProblemLanguageResultExecution timeMemory
673657abysmalCopy and Paste 3 (JOI22_copypaste3)C++14
100 / 100
778 ms98760 KiB
#include<iostream> #include<stdio.h> #include<stdint.h> #include<vector> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> #include<stack> using namespace std; const int64_t INF = (int64_t) 1e18 + 777; const int64_t mINF = 2500 + 5; const int64_t MOD = 1e9 + 9; const int nbit = 11; const int ndig = 10; const int nchar = 26; const int p1 = 31; const int p2 = 53; const int D = 4; int dr[D] = {0, 1, 0, -1}; int dc[D] = {1, 0, -1, 0}; struct Thing { int h1; int h2; int id; Thing(int h1_, int h2_, int id_) : h1(h1_), h2(h2_) ,id(id_) {} bool operator < (const Thing& o) const { if(h1 != o.h1) return h1 > o.h1; else if(h2 != o.h2) return h2 > o.h2; return id < o.id; } }; struct Solution { int n; string s; int64_t a; int64_t b; int64_t c; Solution() {} void solve() { cin >> n >> s >> a >> b >> c; vector<vector<int> > h1(n, vector<int>(n, -1)); vector<vector<int> > h2(n, vector<int>(n, -1)); for(int i = 0; i < n; i++) { int t1 = 0; int t2 = 0; int pow1 = 1; int pow2 = 1; for(int j = i; j < n; j++) { int ch = s[j] - 'a' + 1; t1 = modadd(t1, modmul(ch, pow1)); t2 = modadd(t2, modmul(ch, pow2)); pow1 = modmul(pow1, p1); pow2 = modmul(pow1, p2); h1[i][j] = t1; h2[i][j] = t2; } } vector<vector<int64_t> > dp(n, vector<int64_t>(n, INF)); for(int i = 0; i < n; i++) { dp[i][i] = a; } for(int len = 0; len < n; len++) { set<Thing> st; for(int i = 0; i < n; i++) { int j = i + len; if(j >= n) break; st.insert(Thing(h1[i][j], h2[i][j], i)); } for(int i = 0; i < n; i++) { int j = i + len; if(len == 0 || j >= n) break; dp[i][j] = min(dp[i][j], dp[i][j - 1] + a); if(i != n - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + a); } vector<Thing> tt; for(set<Thing>::iterator it = st.begin(); it != st.end(); it++) { tt.push_back(*(it)); } int k = tt.size(); int tid = 0; vector<int> nx(n, -1); while(tid < k) { pair<int, int> last = make_pair(tt[tid].h1, tt[tid].h2); vector<int> pos; while(tid < k && make_pair(tt[tid].h1, tt[tid].h2) == last) { pos.push_back(tt[tid].id); tid++; } int ps = pos.size(); int r = ps - 1; for(int i = ps - 2; i >= 0; i--) { while(r > 0 && pos[r - 1] > pos[i] + len) r--; if(pos[r] > pos[i] + len) nx[pos[i]] = pos[r]; } } for(int64_t i = 0; i < n; i++) { int64_t l = i; int64_t j = i + len; int64_t cnt = 2; while(nx[l] != -1) { int64_t nl = nx[l]; int64_t nr = nl + len; int64_t x = nr - i + 1 - cnt * (len + 1); dp[i][nr] = min(dp[i][nr], dp[i][j] + b + c * cnt + a * x); cnt++; l = nl; } } } // for(int i = 0; i < n; i++) // { // for(int j = 0; j < n; j++) // { // if(dp[i][j] == INF) cout << "I "; // else cout << dp[i][j] << " "; // } // cout << "\n"; // } cout << dp[0][n - 1]; } int modsub(int t1, int t2) { int res = t1 - t2; if(res < 0) res += MOD; return res; } int modadd(int t1, int t2) { int res = t1 + t2; if(res >= MOD) res -= MOD; return res; } int modmul(int t1, int t2) { int64_t res = 1LL * t1 * t2; return (res % MOD); } bool BIT(int& mask, int& j) { return (mask & MASK(j)); } int MASK(int j) { return (1 << j); } }; void __startup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); } int main() { __startup(); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { Solution().solve(); } return 0; }
#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...