Submission #997379

#	Time	Username	Problem	Language	Result	Execution time	Memory
997379		onbert	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	775 ms	98820 KiB

copypaste3

//bruhed
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, A, B, C;
    string s;
    cin >> n >> s >> A >> B >> C;
    s = '.' + s;
    int id[n+1][n+2], cost[n+1][n+2];
    for (int i=0;i<=n;i++) for (int j=1;j<=n+1;j++) id[i][j] = -1, cost[i][j] = INF;
    for (int i=1;i<=n;i++) cost[1][i] = A;

    for (int sz=1;sz<=n;sz++) {
        // cout << sz << endl;
        if (sz!=1) {
            for (int i=1;i<=n-sz+1;i++) {
                cost[sz][i] = min(cost[sz-1][i] + A, cost[sz][i]);
                cost[sz][i] = min(cost[sz-1][i+1] + A, cost[sz][i]);
                // cout << cost[sz][i] << " ";
            }
        }
        // cout << endl;
        vector<pair<char,int>> v = {{' ', -1}};
        for (int i=1;i<=n-sz+1;i++) v.push_back({s[i], id[sz-1][i+1]});
        sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
        int m = v.size() - 1;
        vector<int> mem[m+1];
        for (int i=1;i<=n-sz+1;i++) {
            id[sz][i] = lower_bound(v.begin(), v.end(), make_pair(s[i], id[sz-1][i+1])) - v.begin();
            mem[id[sz][i]].push_back(i);
        }
        for (int i=1;i<=m;i++) mem[i].push_back(INF);
        for (int i=1;i<=m;i++) {
            for (int J=0;J<(int)mem[i].size()-1;J++) {
                int j = mem[i][J];
                int last = j;
                for (int cnt = 2; ;cnt++) {
                    if (J+cnt-1 > (int)mem[i].size()-1) break;
                    int nxt = max(*lower_bound(mem[i].begin(), mem[i].end(), last + sz), mem[i][J+cnt-1]);
                    if (nxt==INF) break;
                    int SZ = nxt + sz - j;
                    int val = (SZ - cnt*sz)*A + C*cnt + cost[sz][j] + B;
                    // if (SZ == 3 && j == 4) cout << "test " << cnt << " " << val << endl;
                    cost[SZ][j] = min(val, cost[SZ][j]);
                    last = nxt;
                }
            }
        }
    }
    cout << cost[n][1] << endl;
}

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