제출 #1355169

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

copypaste3

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2500+5;

const int mod1 = 1000000093;
int p1 = 53;

const int mod2 = 1e9+7;
int p2 = 31;

array<int, 2> HASH[N][N];
int dp[N][N];
int pre1[N];
int pre2[N];
int n, A, B, C; 
string s;

int powmod(int x, int y, int mod){
    if(!y) return 1;
    int res = powmod(x, y/2, mod);
    if(y%2) return res * res % mod * x % mod;
    return res * res % mod;
}

array<int, 2> get_hash(int l, int r){
    return HASH[l][r];
}

// for(int i=1; i<=n; i++)
void solve(){
    cin >> n >> s >> A >> B >> C;
    s = '%' + s;

    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            HASH[i][j][0] = (HASH[i][j-1][0] + (s[j]-'a'+1)*powmod(p1, i-j, mod1)%mod1)%mod1;
            HASH[i][j][1] = (HASH[i][j-1][1] + (s[j]-'a'+1)*powmod(p2, i-j, mod2)%mod2)%mod2;
        }
    }

    for(int sz=0; sz<=n+1; sz++) for(int i=0; i<=n+1; i++) dp[sz][i] = 1e18;
    for(int sz=1; sz<=n; sz++) dp[sz][sz] = A;
    
    for(int sz=1; sz<=n; sz++){
        vector<int> nxt(n+1, -1);
        map<array<int, 2>, vector<int>> mp;
        for(int i=1; i+sz-1<=n; i++) {
            mp[get_hash(i, i+sz-1)].push_back(i);
        }
        for(int i=1; i+sz-1<=n; i++) {
            auto hash = get_hash(i, i+sz-1);
            auto it = lower_bound(mp[hash].begin(), mp[hash].end(), i+sz);
            if(it == mp[hash].end()) nxt[i] = -1;
            else nxt[i] = *it;
        }


        for(int l=1; l+sz-1<=n; l++){
            int r = l + sz - 1;

            dp[l][r] = min(dp[l][r], min(dp[l][r-1], dp[l+1][r]) + A);

            if(nxt[l] == -1) continue;

            int you = dp[l][r] + B + C;
            int p = nxt[l];
            int end = r;

            while(p != -1 and end <= n){
                you += (p - end - 1)*A + C;
                end = p + sz - 1;
                dp[l][end] = min(dp[l][end], you);
                p = nxt[p];
            }
        }
    }
    cout << dp[1][n];
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

• 서브태스크 1: 1 / 1
• 서브태스크 2: 5 / 5
• 서브태스크 3: 14 / 14
• 서브태스크 4: 10 / 10
• 서브태스크 5: 32 / 32
• 서브태스크 6: 38 / 38