Submission #578601

#TimeUsernameProblemLanguageResultExecution timeMemory
578601InternetPerson10Copy and Paste 3 (JOI22_copypaste3)C++17
57 / 100
3073 ms330284 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; ll ans[2501][2501]; ll num_ma[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; int getCtApps(int x, int y, int i) { if(i < x + ((y - x + 1) / 2)) return 0; if(i >= y) return 1e6; int str_idx = num_ma[i][y]; 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; } int ctApps = 1; 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); } } } return ctApps; } int tot = 0; 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; auto tryI = [&](int i, int ctApps = -1) { if(ctApps == -1) ctApps = getCtApps(x, y, i); if(ctApps == 1e6) return ctApps; int indivChars = y - x - ctApps * (y - i); best = min(best, f(i, y) + b + a * indivChars + c * ctApps); return ctApps; }; int prevCtApps = tryI(y-1); int i = y-1; int lim = x + ((y - x + 1) / 2); while(i >= lim) { int j = 0; int nex = getCtApps(x, y, i-1); if(nex != prevCtApps) { i--; if(i >= lim) { tryI(i, nex); prevCtApps = nex; } continue; } while(nex == prevCtApps) { j++; nex = getCtApps(x, y, i - (1 << j)); } j--; i -= (1 << j); while(j) { j--; if(prevCtApps == getCtApps(x, y, i - (1 << j))) { i -= (1 << j); } } tryI(i, prevCtApps); i--; if(i >= lim) prevCtApps = tryI(i); } 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++) { int x; if(!ma.count(s2)) { x = ma[s2] = ma.size(); apps.push_back(vector<int>()); siz.push_back(j-i); } else x = ma[s2]; apps[x].push_back(i); num_ma[i][j] = x; if(j != n) s2.push_back(s[j]); } } 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:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int j = 0; j < ne.size(); j++) {
      |                    ~~^~~~~~~~~~~
copypaste3.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int k = 0; k < v.size(); k++) {
      |                        ~~^~~~~~~~~~
copypaste3.cpp:138:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             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...