oj.uz

Submission #545906

# Submission time Handle Problem Language Result Execution time Memory
545906 2022-04-05T16:06:24 Z rainboy Popeala (CEOI16_popeala) C
100 / 100
 359 ms 6676 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 884 KB Output is correct
2 Correct 10 ms 852 KB Output is correct
3 Correct 12 ms 876 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1368 KB Output is correct
2 Correct 82 ms 1620 KB Output is correct
3 Correct 81 ms 1976 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 12 ms 884 KB Output is correct
4 Correct 10 ms 852 KB Output is correct
5 Correct 12 ms 876 KB Output is correct
6 Correct 57 ms 1368 KB Output is correct
7 Correct 82 ms 1620 KB Output is correct
8 Correct 81 ms 1976 KB Output is correct
9 Correct 95 ms 2764 KB Output is correct
10 Correct 166 ms 3516 KB Output is correct
11 Correct 235 ms 6296 KB Output is correct
12 Correct 253 ms 6620 KB Output is correct
13 Correct 356 ms 6632 KB Output is correct
14 Correct 327 ms 6628 KB Output is correct
15 Correct 359 ms 6676 KB Output is correct