oj.uz

Submission #875960

# Submission time Handle Problem Language Result Execution time Memory
875960 2023-11-20T21:16:01 Z rainboy Coins (LMIO19_monetos) C
0 / 100
 2000 ms 53760 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];
	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 = 1; 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;
				}
		}
	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;
#if 1
	printf("%d\n", dp[i_][m]);
#else
	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");
	}
#endif
	return 0;
}

Compilation message

monetos.c: In function 'main':
monetos.c:13:22: warning: unused variable 'j_' [-Wunused-variable]
   13 |  int n, m, i, i_, j, j_, s, s_, x;
      |                      ^~
monetos.c:12:23: warning: variable 'cc_' set but not used [-Wunused-but-set-variable]
   12 |  static int cc[N][N], cc_[N][N], dp[N + 1][M + 1];
      |                       ^~~
monetos.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%*d%d%*d%*d", &n), m = n * n / 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~
monetos.c:18:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |    scanf("%d", &cc[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Integer 17 violates the range [0, 1]
2 Incorrect 3 ms 8760 KB Integer 576 violates the range [0, 1]
3 Execution timed out 2028 ms 53760 KB Time limit exceeded
4 Execution timed out 2040 ms 53684 KB Time limit exceeded
5 Execution timed out 2048 ms 53596 KB Time limit exceeded
6 Execution timed out 2029 ms 53592 KB Time limit exceeded
7 Execution timed out 2055 ms 53596 KB Time limit exceeded
8 Execution timed out 2045 ms 53756 KB Time limit exceeded
9 Execution timed out 2047 ms 53592 KB Time limit exceeded
10 Execution timed out 2043 ms 53596 KB Time limit exceeded