Submission #890041

#	Time	Username	Problem	Language	Result	Execution time	Memory
890041		TAhmed33	Copy and Paste 3 (JOI22_copypaste3)	C++98	20 / 100	1330 ms	156072 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[31][31][31][31];
bool pre[31][31][31][31];
string s; ll a, b, c, n;
const ll inf = 1e18;
ll ans (int l1, int r1, int l2, int r2) {
	ll &ret = dp[l1][r1][l2][r2];
	if (ret != -1) return ret;
	if (l1 == 1 && r1 == n) return ret = 0;
	ret = inf;
	if (l1 && r1 != n) ret = min(ret, a + ans(l1, r1 + 1, l2, r2));
	if (!l1) {
		for (int i = 1; i <= n; i++) ret = min(ret, a + ans(i, i, l2, r2));	
	}
	if (l1) ret = min(ret, b + ans(0, 0, l1, r1));
	if (l1 && l2 && r1 + (r2 - l2 + 1) <= n && pre[r1 + 1][r1 + r2 - l2 + 1][l2][r2]) {
		ret = min(ret, c + ans(l1, r1 + r2 - l2 + 1, l2, r2));
	}
	if (!l1 && l2) {
		for (int i = 1; i + (r2 - l2) <= n; i++) {
			if (pre[i][i + r2 - l2][l2][r2]) ret = min(ret, c + ans(i, i + r2 - l2, l2, r2));
		}
	}
	return ret;
}
ll dist[2501][2501];
using matr = array <ll, 3>;
priority_queue <matr, vector <matr>, greater <matr>> pq;
void addedge (ll a, ll b, ll c) {
	if (a < dist[b][c]) {
		dist[b][c] = a;
		pq.push({a, b, c});
	}
}
int main () {
	memset(dp, -1, sizeof(dp));
	cin >> n >> s >> a >> b >> c;
	bool flag = 1;
	s.insert(s.begin(), '0');
	for (int i = 1; i <= n; i++) flag &= s[i] == 'a';
	if (flag) {
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				dist[i][j] = inf;
			}
		}
		dist[0][0] = 0;
		pq.push({0, 0});
		while (!pq.empty()) {
			auto k = pq.top();
			pq.pop();
			if (k[0] > dist[k[1]][k[2]]) continue;
			if (k[1] != n) addedge(k[0] + a, k[1] + 1, k[2]);
			addedge(k[0] + b, 0, k[1]);
			if (k[1] + k[2] <= n) addedge(k[0] + c, k[1] + k[2], k[2]);
		}
		ll mn = inf;
		for (int i = 0; i <= n; i++) mn = min(mn, dist[n][i]);
		cout << (mn == inf ? -1 : mn) << '\n';
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			for (int l = 1; l <= n; l++) {
				for (int m = l; m <= n; m++) {
					if (m - l != j - i) continue;
					pre[i][j][l][m] = 1;
					for (int t = i; t <= j; t++) {
						pre[i][j][l][m] &= s[t] == s[l + t - i];
					}
				}
			}
		}
	}
	cout << ans(0, 0, 0, 0) << '\n';
}

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