제출 #591896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591896		Cross_Ratio	Copy and Paste 3 (JOI22_copypaste3)	C++14	1 / 100	3072 ms	33948 KiB

copypaste3

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
map<string, int> M;
string S;
int D[2505][2505];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    cin >> S;
    int A, B, C;
    cin >> A >> B >> C;
    int i, j;
    for(i=0;i<=N;i++) {
        for(j=0;j<=N;j++) D[i][j] = INF;
    }
    M[""] = 0;
    int L = B / A;
    for(int len = 1; len <= N; len++) {
        for(i=0;i+len<=N;i++) {
            //(  Copy  ) AAA
            if(len==1) {
                D[i][i+len] = A;
                string o = "";
                o+=S[i];
                M[o] = D[i][i+len];
                continue;
            }
            string s = "";
            D[i][i+len] = len * A;
            D[i][i+len] = min(D[i][i+len],min(D[i][i+len-1],D[i+1][i+len])+A);
            for(j=1;j<=len;j++) {
                s+=S[i+j-1];
                if(j<=L) continue;
                if(!M.count(s)) continue;
                int cnt = i + j;
                for(cnt = i+j; cnt < i + len&&S[cnt]==s[(cnt-(i+j))%j]; cnt++);
                int sz = (cnt-i)/j;
                int val = M[s];
                D[i][i+len] = min(D[i][i+len],B + val + C * sz + A * (len - j * sz));
            }
            M[s] = D[i][i+len];
            //cout << i << " to " << i + len << " : " << D[i][i+len] << '\n';
        }
    }
    cout << D[0][N];
}

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