Submission #549182

#	Time	Username	Problem	Language	Result	Execution time	Memory
549182		nonsensenonsense1	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	448 ms	49580 KiB

copypaste3

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>

const int md1 = 1000000787;
const int md2 = 1000000007;
const int g = 37;

inline int add(int a, int b, int md) {
	a += b;
	if (a >= md) a -= md;
	return a;
}
inline int sub(int a, int b, int md) {
	a -= b;
	if (a < 0) a += md;
	return a;
}
inline int mul(int a, int b, int md) {
	return (long long)a * b % md;
}

const int N = 2505;
int n, a, b, c, h1[N], h2[N], next[N];
long long d[N][N];
std::pair<long long, int> str[N];
char s[N];

inline void mnm(long long &a, long long b) {
	a = std::min(a, b);
}

int main() {
	scanf("%d%s%d%d%d", &n, s, &a, &b, &c);
	for (int i = 0; i < n; ++i) {
		h1[i + 1] = add(mul(h1[i], g, md1), s[i] - 'a', md1);
		h2[i + 1] = add(mul(h2[i], g, md2), s[i] - 'a', md2);
	}
	memset(*d, 0x3f, N * N << 3);
	for (int i = 0; i < n; ++i) d[i][i] = 0;
	int gg1 = 1, gg2 = 1;
	for (int l = 1; l <= n; ++l) {
		gg1 = mul(gg1, g, md1);
		gg2 = mul(gg2, g, md2);
		for (int i = 0; i + l <= n; ++i) {
			mnm(d[i][i + l], std::min(d[i][i + l - 1], d[i + 1][i + l]) + a);
			str[i] = std::make_pair((long long)sub(h1[i + l], mul(gg1, h1[i], md1), md1) << 32 | sub(h2[i + l], mul(gg2, h2[i], md2), md2), i);
		}
		std::sort(str, str + n - l + 1);
		for (int i = 0; i + l <= n;) {
			int fi = i, j = i;
			do {
				while (j + l <= n && str[j].first == str[i].first && str[i].second + l > str[j].second) ++j;
				next[i] = j;
				++i;
			} while (i + l <= n && str[i].first == str[i - 1].first);
			for (; fi < i; ++fi) {
				int cnt;
				for (j = fi, cnt = 1; j < i; j = next[j], ++cnt) mnm(d[str[fi].second][str[j].second + l], d[str[fi].second][str[fi].second + l] + b + (long long)cnt * c + (long long)a * (str[j].second + l - str[fi].second - cnt * l));
			}
		}
	}
	printf("%lld\n", d[0][n]);
	return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%s%d%d%d", &n, s, &a, &b, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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