Submission #558014

#	Time	Username	Problem	Language	Result	Execution time	Memory
558014		DanShaders	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	828 ms	54208 KiB

copypaste3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 2510;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll dp[N][N];
int nxt[N][N];

int pref[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	ll a, b, c;
	string s;
	cin >> n >> s >> a >> b >> c;
	for (int i = 0; i < n; ++i) {
		fill(pref, pref + n, 0);
		pref[i] = n - i;
		int zbegin = 0, zend = 0;
		for (int j = i + 1; j < n; ++j) {
			if (zend > j) {
				pref[j] = min(zend - j, pref[i + j - zbegin]);
			}
			while (s[j + pref[j]] == s[i + pref[j]]) {
				++pref[j];
			}
			if (zend < j + pref[j]) {
				zbegin = j;
				zend = j + pref[j];
			}
		}

		int mx = 1;
		for (int j = i + 1; j <= n; ++j) {
			nxt[i][j] = n;
			for (; mx <= min(j - i, pref[j]); ++mx) {
				nxt[i][i + mx] = j;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			dp[i][j] = (j - i) * a;
		}
	}
	for (int len = 1; len <= n; ++len) {
		for (int i = 0; i <= n - len; ++i) {
			int at = nxt[i][i + len];
			ll curr = dp[i][i + len] + b + 2 * c + (at - i - len) * a;
			while (at != n) {
				dp[i][at + len] = min(curr, dp[i][at + len]);
				int prv = at;
				at = nxt[at][at + len];
				curr += c + (at - prv - len) * a;
			}
		}
		if (!(len & (len - 1))) {
			for (int len2 = len; len2 <= n; ++len2) {
				for (int i = 0; i <= n - len2; ++i) {
					dp[i][i + len2] = min({dp[i][i + len2], dp[i][i + len2 - 1] + a, dp[i + 1][i + len2] + a});
				}
			}
		}
	}
	for (int len2 = 1; len2 <= n; ++len2) {
		for (int i = 0; i <= n - len2; ++i) {
			dp[i][i + len2] = min({dp[i][i + len2], dp[i][i + len2 - 1] + a, dp[i + 1][i + len2] + a});
		}
	}
	cout << dp[0][n];
}

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