結果
| 問題 |
No.3097 Azuki Kurai
|
| ユーザー |
👑  ygussany
|
| 提出日時 | 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;
}