Submission #1048814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048814		Andrey	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	159 ms	147444 KiB

copypaste3

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

long long br[2501][2501];
long long dp[2501][2501];
long long pos[2501][2501];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,a,b,d;
    string s;
    cin >> n >> s >> a >> b >> d;
    s = "0"+s;
    for(long long i = 1; i <= n; i++) {
        for(long long j = i+1; j <= n; j++) {
            long long c = 0;
            if(i > 1) {
                c = br[j-1][i-1];
            }
            if(s[i] == s[j]) {
                c++;
            }
            else {
                c = 0;
            }
            c = min(c,j-i);
            br[j][i] = c;
        }
    }
    for(long long i = 1; i <= n; i++) {
        for(long long j = 1; j <= n; j++) {
            pos[i][j] = -1;
        }
        long long y = 1;
        for(long long j = i-1; j >= 1; j--) {
            while(y <= br[i][j]) {
                pos[i][y] = j-y+1;
                y++;
            }
        }
    }
    for(long long i = 1; i <= n; i++) {
        for(long long j = 1; j <= n; j++) {
            dp[i][j] = LLONG_MAX;
        }
        dp[i][i] = a;
        for(long long j = i; j >= 1; j--) {
            if(i != j) {
                dp[j][i] = min(dp[j][i],dp[j+1][i]+a);
                dp[j][i] = min(dp[j][i],dp[j][i-1]+a);
            }
            long long c = j,br = 1;
            while(c >= 1) {
                dp[c][i] = min(dp[c][i],dp[j][i]+br*d+b+a*((i-c+1)-br*(i-j+1)));
                br++;
                c = pos[c+(i-j)][i-j+1];
            }
        }
    }
    cout << dp[1][n];
    return 0;
}

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