結果
問題 | No.3097 Azuki Kurai |
ユーザー |
👑 |
提出日時 | 2025-03-23 14:39:01 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 76 ms / 4,000 ms |
コード長 | 6,151 bytes |
コンパイル時間 | 520 ms |
コンパイル使用メモリ | 31,692 KB |
実行使用メモリ | 20,224 KB |
最終ジャッジ日時 | 2025-04-05 13:05:09 |
合計ジャッジ時間 | 3,735 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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])); | ^~~~~~~~~~~~~~~~~~~~
ソースコード
#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]--; } solve1_ac(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; }