Submission #545906

#	Time	Username	Problem	Language	Result	Execution time	Memory
545906		rainboy	Popeala (CEOI16_popeala)	C11	100 / 100	359 ms	6676 KiB

popeala

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

#define N	20000
#define M	50
#define INF	0x7fffffff

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

int main() {
	static int iii[M + 1][N + 1], ii[M], kk[N + 1], dp[N + 1], dq[N + 1], pp[N + 1];
	static char cc[M][N + 1];
	int n, m, s, h, i, j, k, l;

	scanf("%d%d%d", &m, &n, &s);
	for (i = 1; i <= n; i++) {
		scanf("%d", &pp[i]);
		pp[i] += pp[i - 1];
	}
	for (h = 0; h < m; h++)
		scanf("%s", cc[h]);
	for (l = 0; l <= m; l++) {
		memset(kk, 0, (n + 1) * sizeof *kk);
		memset(ii, -1, m * sizeof *ii);
		for (i = 0, j = 0, k = m; j <= n; j++) {
			while (i < j && k <= l)
				k += kk[i++];
			iii[l][j] = i;
			if (j < n)
				for (h = 0; h < m; h++)
					if (cc[h][j] == '0') {
						if (ii[h] < i)
							k--;
						if (ii[h] != -1)
							kk[ii[h]]--;
						ii[h] = j, kk[j]++;
					}
		}
	}
	for (i = 1; i <= n; i++)
		dp[i] = INF;
	dp[0] = 0;
	while (s--) {
		for (i = 0; i <= n; i++)
			dq[i] = INF;
		for (l = 0; l <= m; l++) {
			long long x;

			x = INF;
			for (i = 0, j = 0; j <= n; j++) {
				while (i < iii[l][j])
					x = min(x, dp[i] == INF ? INF : dp[i] - pp[i] * l), i++;
				if (x != INF)
					dq[j] = min(dq[j], x + pp[j] * l);
			}
		}
		memcpy(dp, dq, (n + 1) * sizeof *dq);
		printf("%d\n", dp[n]);
	}
	return 0;
}

Compilation message (stderr)

popeala.c: In function 'main':
popeala.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d%d", &m, &n, &s);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &pp[i]);
      |   ^~~~~~~~~~~~~~~~~~~
popeala.c:21:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%s", cc[h]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74