Submission #536321

#	Time	Username	Problem	Language	Result	Execution time	Memory
536321		rainboy	도장 모으기 (JOI14_stamps)	C11	10 / 100	20 ms	8588 KiB

stamps

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

#define N	16
#define INF	0x3f3f3f3f

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

int main() {
	static int uu[N + 2], vv[N + 2], dd[N + 2], ee[N + 2], ww[N + 2][N + 2], dp[1 << N][N];
	int n, t, i, j, k, b, ans;

	scanf("%d%d", &n, &t);
	for (i = 1; i <= n; i++)
		scanf("%d%d%d%d", &uu[i], &vv[i], &dd[i], &ee[i]);
	for (i = 0; i <= n + 1; i++)
		for (j = i + 1; j <= n + 1; j++) {
			ww[i][j] = vv[i] + t * (j - i) + uu[j];
			ww[j][i] = j == n + 1 || i == 0 ? INF : ee[j] + t * (j - i) + dd[i];
		}
	for (k = 0; k <= n + 1; k++)
		for (i = 0; i <= n + 1; i++)
			for (j = 0; j <= n + 1; j++)
				ww[i][j] = min(ww[i][j], ww[i][k] + ww[k][j]);
	for (b = 0; b < 1 << n; b++)
		memset(dp[b], 0x3f, n * sizeof *dp[b]);
	for (i = 0; i < n; i++)
		dp[1 << i][i] = ww[0][i + 1];
	for (b = 0; b < 1 << n; b++)
		for (i = 0; i < n; i++) {
			int x = dp[b][i];

			if (x == INF)
				continue;
			for (j = 0; j < n; j++)
				dp[b | 1 << j][j] = min(dp[b | 1 << j][j], x + ww[i + 1][j + 1]);
		}
	ans = INF;
	for (i = 0; i < n; i++)
		ans = min(ans, dp[(1 << n) - 1][i] + ww[i + 1][n + 1]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

stamps.c: In function 'main':
stamps.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
stamps.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%d%d%d", &uu[i], &vv[i], &dd[i], &ee[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 75
• Subtask 3: 0 / 15