제출 #673656

#제출 시각아이디문제언어결과실행 시간메모리
673656abysmalCopy and Paste 3 (JOI22_copypaste3)C++14
62 / 100
621 ms74120 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 p = 61; const int D = 4; int dr[D] = {0, 1, 0, -1}; int dc[D] = {1, 0, -1, 0}; struct Thing { int h; int id; Thing(int h_, int id_) : h(h_), id(id_) {} bool operator < (const Thing& o) const { if(h != o.h) return h > o.h; 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> > h(n, vector<int>(n, -1)); for(int i = 0; i < n; i++) { int tmp = 0; int pow = 1; for(int j = i; j < n; j++) { int ch = s[j] - 'a' + 1; ch = modmul(ch, pow); tmp = modadd(tmp, ch); pow = modmul(pow, p); h[i][j] = tmp; } } 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(h[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) { int last = tt[tid].h; vector<int> pos; while(tid < k && tt[tid].h == 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...