oj.uz

Submission #875954

# Submission time Handle Problem Language Result Execution time Memory
875954 2023-11-20T21:07:09 Z rainboy Coins (LMIO19_monetos) C
20 / 100
 1166 ms 262144 KB 
#include <stdio.h>
#include <string.h>

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

typedef unsigned long long ull;

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

	scanf("%*d%d%*d%*d", &n), m = n * n / 2;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			scanf("%d", &cc[i][j]);
		for (j = 0; j < n; j++)
			cc[i][j] += cc[i][j - 1];
	}
	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;
	}
	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", &n), m = n * n / 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~
monetos.c:19:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |    scanf("%d", &cc[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB K = 17
2 Correct 32 ms 100920 KB K = 576
3 Runtime error 1166 ms 262144 KB Execution killed with signal 9
4 Runtime error 523 ms 262144 KB Execution killed with signal 9
5 Runtime error 64 ms 262144 KB Execution killed with signal 9
6 Runtime error 59 ms 262144 KB Execution killed with signal 9
7 Runtime error 58 ms 262144 KB Execution killed with signal 9
8 Runtime error 61 ms 262144 KB Execution killed with signal 9
9 Runtime error 58 ms 262144 KB Execution killed with signal 9
10 Runtime error 59 ms 262144 KB Execution killed with signal 9