Submission #578601

#	Time	Username	Problem	Language	Result	Execution time	Memory
578601		InternetPerson10	Copy and Paste 3 (JOI22_copypaste3)	C++17	57 / 100	3073 ms	330284 KiB

copypaste3

#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++) {
      |                            ~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 0 / 38