Submission #557998

#	Time	Username	Problem	Language	Result	Execution time	Memory
557998		DanShaders	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	3080 ms	34408 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];

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) {
		for (int j = i + 1; j <= n; ++j) {
			nxt[i][j] = n;
			for (int h = j; h <= n - (j - i); ++h) {
				if (s.substr(i, j - i) == s.substr(h, j - i)) {
					nxt[i][j] = h;
					break;
				}
			}
		}
	}
	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;
			}
		}
		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 i = 0; i < n; ++i) {
		// 	for (int j = 1; j <= n; ++j) {
		// 		cout << dp[i][j] << " ";
		// 	}
		// 	cout << "\n";
		// }
		// cout << endl;
	}
	cout << dp[0][n];
}

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