oj.uz

Submission #875967

# Submission time Handle Problem Language Result Execution time Memory
875967 2023-11-20T21:26:54 Z rainboy Coins (LMIO19_monetos) C
100 / 100
 201 ms 47092 KB 
#include <stdio.h>
#include <string.h>

#define N	150
#define M	(N * N / 2)
#define L	64
#define INF	0x3f3f3f3f

typedef unsigned long long ull;

int main() {
	static int cc[N * 2][N * 2], cc_[N * 2][N * 2], dp[N + 1][M + 1];
	static ull dq[N + 1][M + 1][3];
	int t, n, m, i, i_, j, j_, s, s_, c, x;

	scanf("%d%d%*d%*d", &t, &n);
	if (t <= 2)
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++)
				scanf("%d", &cc[i][j]);
			for (j = 1; j < n; j++)
				cc[i][j] += cc[i][j - 1];
		}
	else {
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++) {
				scanf("%d", &c);
				cc[i / 2][j / 2] += c;
			}
		n /= 2;
		for (i = 0; i < n; i++)
			for (j = 1; j < n; j++)
				cc[i][j] += cc[i][j - 1];
	}
	m = n * n / 2;
	for (i = 0; i <= n; i++)
		memset(dp[i], 0x3f, (m + 1) * sizeof *dp[i]);
	dp[0][0] = 0;
	for (j = n - 1; j >= 0; j--)
		for (i = 0; i < n; i++) {
			i_ = i + 1;
			for (s = i * (j + 1); (s_ = s + j + 1) <= m; s++)
				if (dp[i][s] != INF) {
					s_ = s + j + 1, x = dp[i][s] + cc[i][j];
					if (dp[i_][s_] > x)
						dp[i_][s_] = x, dq[i_][s_][j / L] |= 1ULL << j % L;
				}
		}
	i_ = -1;
	for (i = 0; i <= n; i++)
		if (i_ == -1 || dp[i_][m] > dp[i][m])
			i_ = i;
	for (i = i_; i < n; i++)
		for (j = 0; j < n; j++)
			cc_[i][j] = 1;
	j_ = 0, s_ = m;
	while (i_ > 0) {
		while ((dq[i_][s_][j_ / L] & 1ULL << j_ % L) == 0)
			j_++;
		i_--, s_ -= j_ + 1;
		for (j = 0; j < n; j++)
			cc_[i_][j] = j <= j_ ? 0 : 1;
	}
	if (t > 2) {
		for (i = n - 1; i >= 0; i--)
			for (j = n - 1; j >= 0; j--)
				cc_[i * 2 + 0][j * 2 + 0] = cc_[i * 2 + 0][j * 2 + 1] = cc_[i * 2 + 1][j * 2 + 0] = cc_[i * 2 + 1][j * 2 + 1] = cc_[i][j];
		n *= 2;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			printf("%d ", cc_[i][j]);
		printf("\n");
	}
	return 0;
}

Compilation message

monetos.c: In function 'main':
monetos.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d%*d%*d", &t, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.c:20:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d", &cc[i][j]);
      |     ^~~~~~~~~~~~~~~~~~~~~~
monetos.c:27:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d", &c);
      |     ^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB K = 17
2 Correct 7 ms 19216 KB K = 576
3 Correct 189 ms 46848 KB K = 18623
4 Correct 190 ms 46828 KB K = 21798
5 Correct 159 ms 46676 KB K = 17111
6 Correct 187 ms 47092 KB K = 20841
7 Correct 201 ms 46792 KB K = 21443
8 Correct 147 ms 46848 KB K = 19599
9 Correct 167 ms 46928 KB K = 20754
10 Correct 182 ms 46672 KB K = 20149