Submission #1206710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206710		pinbu	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	299 ms	98496 KiB

copypaste3

// https://codeforces.com/blog/entry/101003?#comment-897398
// https://oj.uz/submission/1096892

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

const int N = 2505;
const long long oo = 1e18;
template<class T> 
	void mini(T &X, T Y) {
		if (X > Y) X = Y;
	}

int n;
long long A, B, C;
string s;
int LCP[N][N], nxt[N][N];
long long dp[N][N];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> s;
    s = ' ' + s;
    cin >> A >> B >> C;
    
    for (int i = n; i; i--) {
    	for (int j = n; j; j--) {
    		LCP[i][j] = (s[i] == s[j]) * (LCP[i + 1][j + 1] + 1);
    		nxt[i][j] = n + 1;
    		dp[i][j] = oo;
    	}
    }
    for (int i = 1; i <= n; i++) {
    	dp[i][i] = A;
    	for (int j = n; j > i; j--) {
    		int len = min(LCP[i][j], j - i);
    		if (len) {
    			mini(nxt[i][len], j);
    		}
    		mini(nxt[i][j - i], nxt[i][j - i + 1]);
    	}
    }
    // finding out how to compute nxt is quite hard...
    for (int len = 1; len <= n; len++) {
    	for (int l = 1; l <= n - len + 1; l++) {
    		int r = l + len - 1;
    		mini(dp[l][r], min(dp[l][r - 1], dp[l + 1][r]) + A);
    		int p = nxt[l][len], num = 2;
    		while (p <= n) {
    			mini(dp[l][p + len - 1], dp[l][r] + B + num * C + (p + len - l - num * len) * A);
    			p = nxt[p][len];
    			num++;
    		}
    	}
    }
    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