Submission #712087

#	Time	Username	Problem	Language	Result	Execution time	Memory
712087		hollwo_pelw	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	486 ms	50548 KiB

copypaste3

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

#define int long long

const int N = 2525, P = 31;

int n, a, b, c, dp[N][N], nxt[N];
char ch[N];
uint64_t hsh[N], f[N], pw[N];

void Hollwo_Pelw(){
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> ch[i];
	
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * P;
		hsh[i] = hsh[i - 1] * P + (ch[i] - 'a' + 1); 
	}

	cin >> a >> b >> c;
	memset(dp, 0x3f, sizeof dp);
	for (int i = 0; i <= n; i++)
		dp[i + 1][i] = 0;
	for (int s = 1; s <= n; s++) {
		for (int l = 1, r = s; r <= n; l++, r++) {
			dp[l][r] = min(dp[l][r], dp[l][r - 1] + a);
			dp[l][r] = min(dp[l][r], dp[l + 1][r] + a);

			f[l] = hsh[r] - hsh[l - 1] * pw[s];
		}

		map<uint64_t, int> lst;
		for (int l = n - s + 1; l >= 1; l--) {
			if (l + s <= n - s + 1)
				lst[f[l + s]] = l + s;
			nxt[l] = lst.count(f[l]) ? lst[f[l]] : n + 1;
		}

		for (int l = 1, r = s; r <= n; l++, r++) {
			for (int L = l, cnt = 1; L + s - 1 <= n; L = nxt[L], cnt ++) {
				dp[l][L + s - 1] = min(dp[l][L + s - 1], dp[l][r] + b + c * cnt + (L + s - l - cnt * s) * a);
			}
		}
	}
	cout << dp[1][n] << '\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