Submission #578561

#TimeUsernameProblemLanguageResultExecution timeMemory
578561InternetPerson10Copy and Paste 3 (JOI22_copypaste3)C++17
25 / 100
3073 ms196008 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<string, int> ma; 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; for(int i = x+1; i < y; i++) { if(a * (y - i) < c) break; int str_idx = ma[s.substr(i, y-i)]; 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 i = 12; i >= 0; i--) { int tent = lift[str_idx][l][i]; if(tent != -1) { if(apps[str_idx][tent] >= x) { l = tent; ctApps += (1 << i); } } } 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++) { for(int j = i+1; j <= n; j++) { string s2 = s.substr(i, j-i); if(!ma.count(s2)) { ma[s2] = ma.size(); apps.push_back(vector<int>()); siz.push_back(j-i); } apps[ma[s2]].push_back(i); } } 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].resize(13); lift[j][k][0] = ne[j][k]; } for(int l = 1; l < 13; l++) { for(int k = 0; k < v.size(); k++) { 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]; } } } cout << (ll)f(0, n) << '\n'; }

Compilation message (stderr)

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