Submission #642859

#	Time	Username	Problem	Language	Result	Execution time	Memory
642859		rainboy	Copy and Paste 3 (JOI22_copypaste3)	C11	100 / 100	310 ms	58288 KiB

copypaste3

#include <stdio.h>
#include <string.h>

#define N	2500
#define A	26
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

int main() {
	static char cc[N + 1];
	static long long dp[N][N];
	static int lcp[N + 1][N + 1], ii[N + 1], jj[N + 1], kk[A + 1];
	int n, i, j, k, l, a;
	long long u, v, w;

	scanf("%d%s%lld%lld%lld", &n, cc, &u, &v, &w);
	for (i = n - 1; i >= 0; i--)
		for (j = n - 1; j >= 0; j--)
			lcp[i][j] = cc[i] == cc[j] ? lcp[i + 1][j + 1] + 1 : 0;
	for (i = 0; i < n; i++)
		memset(dp[i] + i, 0x3f, (n - i + 1) * sizeof *dp[i]), dp[i][i] = u;
	for (i = 0; i <= n; i++)
		ii[i] = i;
	for (l = 1; l < n; l++) {
		memset(kk, 0, (A + 1) * sizeof *kk);
		for (i = 0; i <= n - l + 1; i++) {
			j = --ii[i];
			if (j < 0)
				continue;
			kk[cc[j] - 'a' + 1]++;
		}
		for (a = 1; a <= A; a++)
			kk[a] += kk[a - 1];
		for (i = 0; i <= n - l + 1; i++)
			if ((j = ii[i]) >= 0)
				jj[kk[cc[j] - 'a']++] = j;
		memcpy(ii, jj, (n - l + 1) * sizeof *jj);
		memset(jj, -1, n * sizeof *jj);
		for (i = 0, j = 0; i < n - l + 1; i++) {
			while (j < n - l + 1 && (j < i || lcp[ii[i]][ii[j]] >= l && ii[j] - ii[i] < l))
				j++;
			if (j < n - l + 1 && lcp[ii[i]][ii[j]] >= l)
				jj[ii[i]] = ii[j];
		}
		for (i = 0; (j = i + l - 1) < n; i++) {
			long long x = dp[i][j];

			if (x == INF)
				continue;
			if (i > 0)
				dp[i - 1][j] = min(dp[i - 1][j], x + u);
			if (j + 1 < n)
				dp[i][j + 1] = min(dp[i][j + 1], x + u);
			for (j = jj[i], k = 2; j != -1; j = jj[j], k++)
				dp[i][j + l - 1] = min(dp[i][j + l - 1], x + u * (j - i + l - k * l) + v + w * k);
		}
	}
	printf("%lld\n", dp[0][n - 1]);
	return 0;
}

Compilation message (stderr)

copypaste3.c: In function 'main':
copypaste3.c:41:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |    while (j < n - l + 1 && (j < i || lcp[ii[i]][ii[j]] >= l && ii[j] - ii[i] < l))
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
copypaste3.c:17:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%d%s%lld%lld%lld", &n, cc, &u, &v, &w);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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