제출 #1120117

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

copypaste3

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

vector<int> z_function(const string& s){
    int n = (int)s.size();
    vector<int> z(n);

    for(int i = 1, l = 0, r = 0; i < n; ++i){
        z[i] = max(0, min(r - i, z[i - l]));
        while(i + z[i] < n && s[i + z[i]] == s[z[i]]) ++z[i];
        if(i + z[i] > r){
            l = i; r = i + z[i];
        }
    }
    return z;
}

const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N; long long A, B, C;
    string S;

    cin >> N >> S >> A >> B >> C;
    vector<vector<int>> next(N + 1, vector<int>(N + 1, N));

    for(int i = N - 1; i >= 0; --i){
        vector<int> z = z_function(S.substr(i, N - i));
//        for(int j : z) cout << j << ' '; cout << '\n';
        int mx = 0;
        for(int j = i + 1; j < N; ++j){
            int extend = min(j - i, z[j - i]);
            while(mx < extend){
                ++mx;
                next[i][i + mx] = j;
            }
        }
    }

//    for(int i = 0; i < N; ++i){
//        for(int j = i + 1; j <= N; ++j){
//            if(next[i][j] != N){
//                cout << dbg(i) << dbg(j) << dbg(next[i][j]) << '\n';
//            }
//        }
//    }

    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, inf));

    for(int i = 0; i < N; ++i) dp[i][i + 1] = A + B;

    for(int len = 1; len <= N; ++len){
        for(int i = 0, j = len; j <= N; ++i, ++j){
            minimize(dp[i][j], dp[i][j - 1] + A);
            minimize(dp[i][j], dp[i + 1][j] + A);

            int len = j - i;
            int pos = next[i][j];
            int cnt_paste = 1;
            while(pos < N){
//                assert(pos - i - cnt_paste * len >= 0);
                minimize(dp[i][pos + len], dp[i][j] + (1 + cnt_paste) * C + (pos - i - cnt_paste * len) * A + B);
                pos = next[pos][pos + len];
                ++cnt_paste;
            }
        }
    }

    cout << dp[0][N] - B << '\n';

    return 0;
}

/*

next[l][r] = minimum k that s[l...r) = s[k...k + (r - l))
dp[l][r] = minimum cost to make X = "", Y = s[l...r)

*/

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