제출 #796312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796312		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++17	0 / 100	1 ms	456 KiB

copypaste3

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2500;
const ll INF = 1e18;

ll dp[N][N];
pair<ll, ll> pr[N][N];

void modify(int i, int j, int l, int r, ll val) {
    if(dp[i][j] <= val + dp[l][r]) return;
    dp[i][j] = val + dp[l][r];
    pr[i][j] = {l, r};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll A, B, C;
    cin >> A >> B >> C;
    for(int i = 0; i < n; i++) {
        dp[i][i] = A;
    }
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            dp[i][j] = INF;
            pr[i][j] = {-1, -1};
        }
    }
    for(int l = n - 1; l >= 0; l--) {
        int pf[n] = {};
        pf[l] = 0;
        for(int i = l + 1; i < n; i++) {
            pf[i] = pf[i - 1];
            while(pf[i] && s[l + pf[i]] != s[i]) {
                pf[i] = pf[l + pf[i] - 1];
            }
            if(s[l + pf[i]] == s[i]) pf[i]++;
        }
        for(int r = l; r < n; r++) {
            if(l) modify(l - 1, r, l, r, A);
            if(r < n - 1) modify(l, r + 1, l, r, A);
            int len = r - l + 1;
            int lb = r + len, k = 1;
            while (lb < n) {
                if(pf[lb] == len) {
                    k++;
                    modify(l, lb, l, r, B + C * k + (lb - l + 1 - len * k) * A);
                    lb += len;
                } else lb++;
            }
        }
    }
    // for(int len = 1; len <= n; len++) {
    //     for(int l = 0; l <= n - len; l++) {
    //         cout << "(" << l << ' ' << l + len - 1 << ")" << dp[l][l + len - 1] << ' ' << pr[l][l + len - 1].first << ' ' << pr[l][l + len - 1].second << " . "; 
    //     }
    //     cout << '\n';
    // }
    cout << dp[0][n - 1];
}

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