Submission #810606

#	Time	Username	Problem	Language	Result	Execution time	Memory
810606		rainboy	Netrpeljivost (COI23_netrpeljivost)	C11	100 / 100	861 ms	95400 KiB

Main

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

#define N	2048
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int main() {
	static int ww[N][N];
	static long long dp[N][N], dq[N][N], xx[N];
	int n, h, i, j, k, l, m, r, lm, mr;
	long long ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &ww[i][j]);
	if (n == 1) {
		printf("0\n");
		return 0;
	}
	if (n == 2) {
		printf("%d\n", ww[0][1]);
		return 0;
	}
	for (h = 0; 1 << h < n / 2; h++)
		if (h == 0)
			for (i = 0; i < n; i += 2) {
				j = i + 1;
				dp[i][j] = ww[i][j];
			}
		else
			for (l = 0; l < n; l = r) {
				r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
				for (i = l; i < m; i++)
					memset(dq[i] + m, 0x3f, (r - m) * sizeof *dq[i]);
				for (i = l; i < lm; i++)
					for (j = lm; j < m; j++)
						for (k = m; k < r; k++) {
							dq[i][k] = min(dq[i][k], dp[i][j] + ww[j][k]);
							dq[j][k] = min(dq[j][k], dp[i][j] + ww[i][k]);
						}
				for (i = l; i < m; i++)
					memset(dp[i] + m, 0x3f, (r - m) * sizeof *dp[i]);
				for (i = l; i < m; i++)
					for (j = m; j < mr; j++)
						for (k = mr; k < r; k++) {
							dp[i][k] = min(dp[i][k], dq[i][j] + dp[j][k]);
							dp[i][j] = min(dp[i][j], dq[i][k] + dp[j][k]);
						}
			}
	l = 0, r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
	memset(xx + l, 0x3f, (r - l) * sizeof *xx);
	for (i = l; i < lm; i++)
		for (j = lm; j < m; j++) {
			xx[i] = min(xx[i], dp[i][j]);
			xx[j] = min(xx[j], dp[i][j]);
		}
	for (i = m; i < mr; i++)
		for (j = mr; j < r; j++) {
			xx[i] = min(xx[i], dp[i][j]);
			xx[j] = min(xx[j], dp[i][j]);
		}
	ans = INF;
	for (i = l; i < m; i++)
		for (j = m; j < r; j++)
			ans = min(ans, xx[i] + ww[i][j] + xx[j]);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:35:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   35 |     r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
      |                   ~~^~~
Main.c:35:62: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |     r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
      |                                                            ~~^~~
Main.c:35:85: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |     r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
      |                                                                                   ~~^~~
Main.c:53:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   53 |  l = 0, r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
      |                       ~~^~~
Main.c:53:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |  l = 0, r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
      |                                                                ~~^~~
Main.c:53:89: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |  l = 0, r = l + (1 << h + 1), m = l + (1 << h), lm = l + (1 << h - 1), mr = m + (1 << h - 1);
      |                                                                                       ~~^~~
Main.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:18:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |    scanf("%d", &ww[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 17 / 17
• Subtask 3: 32 / 32
• Subtask 4: 41 / 41