Submission #776883

#	Time	Username	Problem	Language	Result	Execution time	Memory
776883		aZvezda	Copy and Paste 3 (JOI22_copypaste3)	C++14	25 / 100	3063 ms	60280 KiB

copypaste3

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define cerr if(false)cerr

const ll MAX_N = 2510;
ll n, a, b, c;
string str;

ll dp[MAX_N][MAX_N][2];

ll solve(ll l, ll r, bool clip) {
	if(!clip) { return (r - l + 1) * a; }
	if(dp[l][r][clip] != -1) { return dp[l][r][clip]; }
	if(l == r) { return a; }
	ll &ans = dp[l][r][clip];
	ans = (r - l + 1) * a;
	ans = min(ans, solve(l + 1, r, true) + a);
	ans = min(ans, solve(l + 1, r, false) + a);
	cerr << "----------------------" << endl;
	for(ll len = 1; len <= (r - l + 1); len ++) {
		string now = str.substr(l, len);
		ll pos = l;
		ll total = solve(l, l + len - 1, true) + b;
		cerr << "Starting " << total << endl;
		while(pos <= r) {
			if(pos + len - 1 <= r && str.substr(pos, len) == now) {
				pos += len; 
				total += c;
				cerr << "p";
			} else {
				pos ++;		
				total += a;
				cerr << "w";
			}
		}
		total += max(0ll, r - pos + 1) * a;
		ans = min(ans, total);
		cerr << " For llerval " << l << " " << r 
			<< " " << len << " " << total << endl;
	}	
	cerr << l << " " << r << " " << str.substr(l, r - l + 1) << " "
		<< clip << " " << ans << endl;
	return ans;
}

signed main() {

	cin >> n >> str >> a >> b >> c;

	for(ll i = 0; i < n; i ++) {
		for(ll j = 0; j < n; j ++) {
			dp[i][j][0] = dp[i][j][1] = -1;
		}		
	}

	cout << solve(0, n - 1, true) << endl;
	
    return 0;
}

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