Submission #549177

#	Time	Username	Problem	Language	Result	Execution time	Memory
549177		nonsensenonsense1	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	330 ms	49504 KiB

copypaste3

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

const int md = 1000000007;
const int g = 44;

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

const int N = 2505;
int n, a, b, c, h[N], next[N];
long long d[N][N];
std::pair<int, 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) h[i + 1] = add(mul(h[i], g), s[i] - 'a');
	memset(*d, 0x3f, N * N << 3);
	for (int i = 0; i < n; ++i) d[i][i] = 0;
	int gg = 1;
	for (int l = 1; l <= n; ++l) {
		gg = mul(gg, g);
		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(sub(h[i + l], mul(gg, h[i])), 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:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  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: 0 / 38