#1058776 (C) No.3097 Azuki Kurai

提出ソース

結果

問題	No.3097 Azuki Kurai
ユーザー	👑 ygussany
提出日時	2025-03-23 14:39:28
言語	C (gcc 13.3.0)
結果	AC
実行時間	2,383 ms / 4,000 ms
コード長	6,153 bytes
コンパイル時間	1,690 ms
コンパイル使用メモリ	31,420 KB
実行使用メモリ	7,720 KB
最終ジャッジ日時	2025-04-05 12:48:30
合計ジャッジ時間	75,431 ms
ジャッジサーバーID （参考情報）	judge5 / judge6

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 32

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.c: In function ‘main’:
main.c:159:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  159 |         scanf("%d %d %d", &N, &M, &K);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:160:33: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  160 |         for (i = 0; i < N; i++) scanf("%d", &(A[i]));
      |                                 ^~~~~~~~~~~~~~~~~~~~
main.c:162:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  162 |                 scanf("%d", &(B[i]));
      |                 ^~~~~~~~~~~~~~~~~~~~

ソースコード

raw source code

#include <stdio.h>

#define N_MAX 10
#define M_MAX 2000
#define bit_N_MAX (1 << N_MAX)

const int bit[25] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216};
const long long sup = 1LL << 60;

void chmin(long long *a, long long b)
{
	if (*a > b) *a = b;
}

void solve1_ac(int N, int M, int K, int A[], int B[], long long ans[])
{
	int i, j, k, kk, l, cur, prev, sum[N_MAX] = {};
	static int q[N_MAX][bit_N_MAX][bit_N_MAX][2], n[N_MAX][bit_N_MAX];
	static long long dp[2][bit_N_MAX], tmp;
	for (i = 0; i < N; i++) {
		for (k = 0; k < bit[N]; k++) {
			n[i][k] = 0;
			// printf("%d %d: ", i, k);
			for (kk = ((k & bit[i]) != 0)? k ^ bit[i]: k, l = kk; l < bit[N]; l = (l + 1) | kk) {
				if ((l & bit[i]) != 0) continue;
				for (j = 0; j < N; j++) if ((k & bit[(j-1+N)%N]) == 0 && (k & bit[j]) == 0 && (k & bit[(j+1)%N]) == 0 && (l & bit[j]) != 0) break;
				if (j == N) {
					q[i][k][n[i][k]][0] = l;
					for (j = 0, q[i][k][n[i][k]][1] = 0; j < N; j++) if ((k & bit[j]) != 0 && ((i != (j - 1 + N) % N && (l & bit[(j-1+N)%N]) == 0) || (i != (j + 1) % N && (l & bit[(j+1)%N]) == 0))) q[i][k][n[i][k]][1]++;
					// printf("(%d %d) ", q[i][k][n[i][k]][0], q[i][k][n[i][k]][1]);
					n[i][k]++;
				}
			}
			// sum[i] += n[i][k];
			// printf("\n");
		}
	}
	// printf("[%d %d] ", sum[0], sum[1]);
	for (k = 0; k < bit[N]; k++) for (j = 0, dp[0][k] = 0; j < N; j++) if ((k & bit[j]) == 0) dp[0][k] += A[j];
	for (i = 1, cur = 1, prev = 0; i <= M; i++, cur ^= 1, prev ^= 1) {
		for (k = 0; k < bit[N]; k++) dp[cur][k] = sup;
		for (k = 0; k < bit[N]; k++) {
			for (kk = 0; kk < n[B[i]][k]; kk++) {
				l = q[B[i]][k][kk][0];
				tmp = dp[prev][k] + (long long)K * q[B[i]][k][kk][1];
				chmin(&(dp[cur][l]), tmp);
			}
		}
		ans[i] = dp[cur][0];
		// for (k = 0; k < bit[N]; k++) printf("(%d %lld) ", k, dp[cur][k]);
		// printf("\n");
	}
}

void solve2_slow(int N, int M, int K, int A[], int B[], long long ans[])
{
	int i, j, k, kk, l, cur, prev;
	static long long dp[2][bit_N_MAX], tmp;
	for (k = 0; k < bit[N]; k++) for (j = 0, dp[0][k] = 0; j < N; j++) if ((k & bit[j]) == 0) dp[0][k] += A[j];
	for (i = 1, cur = 1, prev = 0; i <= M; i++, cur ^= 1, prev ^= 1) {
		for (k = 0; k < bit[N]; k++) dp[cur][k] = sup;
		for (k = 0; k < bit[N]; k++) {
			for (kk = ((k & bit[B[i]]) != 0)? k ^ bit[B[i]]: k, l = kk; l < bit[N]; l = (l + 1) | kk) {
				tmp = dp[prev][k];
				for (j = 0; j < N; j++) if ((k & bit[j]) != 0 && ((B[i] != (j - 1 + N) % N && (l & bit[(j-1+N)%N]) == 0) || (B[i] != (j + 1) % N && (l & bit[(j+1)%N]) == 0))) tmp += K;
				chmin(&(dp[cur][l]), tmp);
			}
		}
		ans[i] = dp[cur][0];
		// for (k = 0; k < bit[N]; k++) printf("(%d %lld) ", k, dp[cur][k]);
		// printf("\n");
	}
}

void solve3_wa(int N, int M, int K, int A[], int B[], long long ans[])
{
	int i, j, k, l;
	static long long dp[bit_N_MAX], tmp;
	for (k = 0; k < bit[N]; k++) for (j = 0, dp[k] = 0; j < N; j++) if ((k & bit[j]) == 0) dp[k] += A[j];
	for (i = 1; i <= M; i++) {
		for (k = 0; k < bit[N]; k++) {
			if ((k & bit[B[i]]) != 0) {
				l = k ^ bit[B[i]];
				tmp = dp[k];
				for (j = 0; j < N; j++) if ((k & bit[j]) != 0 && ((B[i] != (j - 1 + N) % N && (l & bit[(j-1+N)%N]) == 0) || (B[i] != (j + 1) % N && (l & bit[(j+1)%N]) == 0))) tmp += K;
				chmin(&(dp[l]), tmp);
			}
			for (j = 0; j < N; j++) if ((k & bit[j]) != 0 && ((B[i] != (j - 1 + N) % N && (k & bit[(j-1+N)%N]) == 0) || (B[i] != (j + 1) % N && (k & bit[(j+1)%N]) == 0))) dp[k] += K;
		}
		ans[i] = dp[0];
		for (k = 0; k < bit[N]; k++) printf("(%d %lld) ", k, dp[k]);
		printf("\n");
	}
}

#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL

static unsigned int mt[MT_N];
static int mti = MT_N + 1;

void init_genrand(unsigned int s)
{
    mt[0] = s & 0xffffffffUL;
    for (mti = 1; mti < MT_N; mti++) {
        mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        mt[mti] &= 0xffffffffUL;
    }
}

unsigned int genrand()
{
    unsigned int y;
    static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};

    if (mti >= MT_N) {
        int kk;
        if (mti == MT_N + 1) init_genrand(5489UL);
		
        for (kk = 0; kk < MT_N - MT_M; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        for (; kk < MT_N - 1; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];

        mti = 0;
    }
  
    y = mt[mti++];

    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

int create_random_instance(int N, int M, int A[], int B[])
{
	int i;
	for (i = 0; i < N; i++) A[i] = genrand() % 11;
	for (i = 1; i <= M; i++) B[i] = genrand() % N;
	return genrand() % 3 + 1;
}

int main()
{
	int i, N, M, K, A[N_MAX + 1], B[M_MAX + 1];
	long long ans[M_MAX + 1];
	scanf("%d %d %d", &N, &M, &K);
	for (i = 0; i < N; i++) scanf("%d", &(A[i]));
	for (i = 1; i <= M; i++) {
		scanf("%d", &(B[i]));
		B[i]--;
	}
	solve2_slow(N, M, K, A, B, ans);
	for (i = 1; i <= M; i++) printf("%lld\n", ans[i]);
	
	/*
	int i, N, M, K, A[N_MAX + 1], B[M_MAX + 1], k = 0, kk = 1;
	long long ans[2][M_MAX + 1];
	scanf("%d %d", &N, &M);
	while (1) {
		K = create_random_instance(N, M, A, B);
		solve(N, M, K, A, B, ans[0]);
		solve2(N, M, K, A, B, ans[1]);
		for (i = 1; i <= M; i++) if (ans[0][i] != ans[1][i]) break;
		if (i <= M) {
			printf("\n");
			printf("%d %d %d\n", N, M, K);
			for (i = 0; i < N; i++) printf("%d ", A[i]);
			printf("\n");
			for (i = 1; i <= M; i++) printf("%d ", B[i] + 1);
			printf("\n");
			for (i = 1; i <= M; i++) printf("%lld %lld\n", ans[0][i], ans[1][i]);
			break;
		}
		
		k++;
		if (k == kk) {
			printf("%d ", k);
			kk <<= 1;
		}
	}
	*/
	
	fflush(stdout);
	return 0;
}

yukicoder

結果

コンパイルメッセージ

ソースコード