Submission #578569

#TimeUsernameProblemLanguageResultExecution timeMemory
578569InternetPerson10Copy and Paste 3 (JOI22_copypaste3)C++17
25 / 100
3081 ms151616 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; ll ans[2501][2501]; int n; string s; ll a, b, c; map<pair<int, int>, pair<int, int>> other_ans; map<string, int> ma, revma; vector<vector<int>> apps; vector<vector<int>> ne; vector<vector<vector<int>>> lift; vector<int> siz; ll f(int x, int y) { if(ans[x][y] != -1) return ans[x][y]; if(y - x == 1) { return ans[x][y] = a; } ll best = f(x, y-1) + a; string s_in = s.substr(x + (y - x + 1) / 2, y - (x + (y - x + 1) / 2)); reverse(s_in.begin(), s_in.end()); for(int i = x + (y - x + 1) / 2; i < y; i++) { if(a * (y - i) < c) break; int str_idx = revma[s_in]; s_in.pop_back(); int l = 0, r = apps[str_idx].size(); while(l != r - 1) { int mid = (l + r) / 2; if(apps[str_idx][mid] <= i) l = mid; else r = mid; } assert(apps[str_idx][l] == i); int ctApps = 1; // Optimize with binary lifting if this is right /* while(apps[str_idx][l] >= x) { ctApps++; l = ne[str_idx][l]; if(l == -1) break; } */ // Optimized for(int z = lift[str_idx][l].size() - 1; z >= 0; z--) { int tent = lift[str_idx][l][z]; if(tent != -1) { if(apps[str_idx][tent] >= x) { l = tent; ctApps += (1 << z); } } } int indivChars = y - x - ctApps * (y - i); best = min(best, f(i, y) + b + a * indivChars + c * ctApps); } return ans[x][y] = best; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> s >> a >> b >> c; for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { ans[i][j] = -1; } } for(int i = 0; i < n; i++) { string s2 = s.substr(i, 1); for(int j = i+1; j <= n; j++) { if(!ma.count(s2)) { ma[s2] = ma.size(); apps.push_back(vector<int>()); siz.push_back(j-i); } apps[ma[s2]].push_back(i); if(j != n) s2.push_back(s[j]); } } for(auto p : ma) { string s2 = p.first; reverse(s2.begin(), s2.end()); revma[s2] = p.second; } ne = apps; lift.resize(ne.size()); for(int j = 0; j < ne.size(); j++) { lift[j].resize(ne[j].size()); vector<int> v = ne[j]; queue<int> q; for(int i = v.size() - 1; i >= 0; i--) { q.push(i); int g = q.front(); while(v[g] - v[i] >= siz[j]) { q.pop(); ne[j][g] = i; g = q.front(); } } while(q.size()) { int g = q.front(); q.pop(); ne[j][g] = -1; } for(int k = 0; k < v.size(); k++) { lift[j][k].push_back(ne[j][k]); } for(int l = 1; l < 13; l++) { for(int k = 0; k < v.size(); k++) { lift[j][k].push_back(-1); if(lift[j][k][l-1] == -1) lift[j][k][l] = -1; else lift[j][k][l] = lift[j][lift[j][k][l-1]][l-1]; } if(lift[j].back()[l] == -1) break; } } cout << (ll)f(0, n) << '\n'; }

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int j = 0; j < ne.size(); j++) {
      |                    ~~^~~~~~~~~~~
copypaste3.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int k = 0; k < v.size(); k++) {
      |                        ~~^~~~~~~~~~
copypaste3.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int k = 0; k < v.size(); k++) {
      |                            ~~^~~~~~~~~~
#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...