Submission #544500

#	Time	Username	Problem	Language	Result	Execution time	Memory
544500		model_code	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	798 ms	73728 KiB

copypaste3

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	(void) n;
	std::string s;
	std::cin >> s;
	int64_t a = ri();
	int64_t b = ri();
	int64_t c = ri();
	
	/*
		next[l][r] : 
			smallest k such that k >= r && s.substr(l, r - l) == s.substr(k, r - l)
			n if no such k exists
	*/
	int next[n][n + 1];
	auto z = [] (char *s) { // z algorithm : returns the Z array of the string starting at `s`
		int n = strlen(s);
		std::vector<int> res(n);
		int head = 0;
		int start = 0;
		for (int i = 1; i < n; i++) {
			if (res[i - start] >= head - i) {
				head = std::max(head, i);
				while (head < n && s[head] == s[head - i]) head++;
				res[i] = head - i;
				start = i;
			} else res[i] = std::min(n - i, res[i - start]);
		}
		return res;
	};
	for (int i = 0; i < n; i++) {
		auto tmp = z(&s[i]);
		int max_len = 0;
		for (int j = i + 1; j < n; j++) {
			int cur_max_len = std::min(j - i, tmp[j - i]);
			while (max_len < cur_max_len) next[i][i + ++max_len] = j;
		}
		while (max_len < n - i) next[i][i + ++max_len] = n;
	}
	
	int64_t dp[n][n + 1]; // dp[l][r] : the lowest cost to make x == "" && y == s.substr(l, r - l)
	for (auto &i : dp) for (auto &j : i) j = 1000000000000000000;
	
	for (int i = 0; i < n; i++) dp[i][i + 1] = a + b;
	for (int len = 1; len < n; len++) {
		for (int l = 0; l + len <= n; l++) {
			int r = l + len;
			if (l) dp[l - 1][r] = std::min(dp[l - 1][r], dp[l][r] + a);
			if (r + 1 <= n) dp[l][r + 1] = std::min(dp[l][r + 1], dp[l][r] + a);
			
			int cur = l;
			int cnt = 1; // number of pasting
			while (next[cur][cur + len] < n) {
				cur = next[cur][cur + len];
				++cnt;
				dp[l][cur + len] = std::min(dp[l][cur + len], dp[l][r] + c * cnt + a * (cur + len - l - len * cnt) + b);
			}
		}
	}
	// dp[0][n] is the cost to make x == "" && y == s (immediately after cutting).
	// To make x == s, the last cutting is unnecessary
	printf("%" PRId64 "\n", dp[0][n] - b);
	return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int ri()':
copypaste3.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |  scanf("%d", &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