제출 #1289496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289496		Icelast	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	287 ms	74160 KiB

copypaste3

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}
void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    ll A, B, C;
    cin >> A >> B >> C;
    auto chmin = [&](ll &a, ll b) -> void{
        a = min(a, b);
    };
    vector<vector<ll>> f(n+2, vector<ll>(n+2, INF));
    for(int i = 1; i <= n+1; i++){
        f[i][i-1] = 0;
    }
    vector<vector<int>> link(n+1, vector<int>(n+1));
    for(int l = n; l >= 1; l--){
        vector<int> z(n+1, 0);
        vector<int> t = z_function(s.substr(l, n-l+1));
        for(int i = l; i <= n; i++){
            z[i] = t[i-l];
        }
        int j = l;
        for(int len = 1; len <= n-l+1; len++){
            chmin(f[l][l+len-1], f[l+1][l+len-1] + A);
            chmin(f[l][l+len-1], f[l][l+len-1-1] + A);
            j = max(j, l+len);
            while(j <= n && z[j] < len){
                j++;
            }
            link[l][len] = j;
            int r = link[l][len];
            int cnt = 1;
            while(r <= n){
                cnt++;
                chmin(f[l][r+len-1], f[l][l+len-1] + B + C * cnt + A * ((r+len-1 - l + 1) - (len*cnt)));
                r = link[r][len];
            }
        }
    }
    cout << f[1][n];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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