Submission #547414

#	Time	Username	Problem	Language	Result	Execution time	Memory
547414		skittles1412	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	917 ms	342816 KiB

copypaste3

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const long mod = 1e9 + 7;

long bpow(long base, long exp) {
	long ans = 1;
	while (exp) {
		if (exp & 1) {
			ans = (ans * base) % mod;
		}
		base = (base * base) % mod;
		exp >>= 1;
	}
	return ans;
}

long inv(long x) {
	return bpow(x, mod - 2);
}

struct Hasher {
	int n;
	vector<long> psum, ipow;

	Hasher(const string& s, long base) : n(sz(s)), psum(n + 1), ipow(n + 1) {
		ipow[0] = 1;
		long ibase = inv(base), exp = 1;
		for (int i = 0; i < n; i++) {
			psum[i + 1] = (psum[i] + (s[i] - 'a' + 1) * exp) % mod;
			exp = (exp * base) % mod;
			ipow[i + 1] = (ipow[i] * ibase) % mod;
		}
	}

	long hash(int l, int r) const {
		return (psum[r] - psum[l] + mod) * ipow[l] % mod;
	}
};

struct H {
	Hasher h1, h2;

	H(const string& s) : h1(s, 31), h2(s, 29) {}

	long hash(int l, int r) const {
		return h1.hash(l, r) * mod + h2.hash(l, r);
	}
};

void solve1(int n, long wa, long wb, long wc) {
	long dp[n + 1];
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = wa * i;
		for (int j = 1; j < i; j++) {
			int cnt = i / j;
			dp[i] = min(dp[i], wa * i + dp[j] + wb + cnt * (wc - wa * j));
		}
	}
	cout << dp[n] << endl;
}

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	long wa, wb, wc;
	cin >> wa >> wb >> wc;
	{
		for (auto& a : s) {
			if (a != 'a') {
				goto loop;
			}
		}
		solve1(n, wa, wb, wc);
		return;
	loop:;
	}
	H h(s);
	pair<int, int> mp[n][n];
	for (int i = 1; i <= n; i++) {
		map<long, pair<int, int>> m;
		for (int j = n - i; j >= 0; j--) {
			mp[j][j + i - 1] =
				m.emplace(h.hash(j, j + i), pair<int, int> {j, j + i - 1}).first->second;
		}
	}
	long dp[n][n], mn[n];
	memset(mn, 0x3f, sizeof(mn));
	vector<pair<int, int>> occ[n][n];
	for (int l = n - 1; l >= 0; l--) {
		long copt = 0;
		for (int r = l; r < n; r++) {
			copt = min(copt + wa, wa * (r - l + 1) + mn[r]);
			dp[l][r] = copt;
			{
				auto [il, ir] = mp[l][r];
				int len = r - l + 1;
				int nbs =
					int(occ[il][ir].rend() - lower_bound(occ[il][ir].rbegin(), occ[il][ir].rend(),
														 pair<int, int> {l + len, -100})) -
					1;
				int ci = sz(occ[il][ir]), x = 0;
				occ[il][ir].emplace_back(l, nbs);
				while (ci != -1) {
					auto [pos, nxt] = occ[il][ir][ci];
					int np = pos + len - 1;
					x++;
					mn[np] = min(mn[np], dp[il][ir] + wb + x * (wc - wa * len));
					ci = nxt;
				}
			}
		}
	}
	cout << dp[0][n - 1] << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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