(cache)Submission #66236571 - AtCoder Beginner Contest 404

Contest Duration: 2025-05-03(Sat) 21:00 - 2025-05-03(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66236571

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
int N, M;
int C[16];
int K[128];
int A[128][16];
uint64_t target[2];
uint64_t offer[128][2];
int main(void) {
  int i, j;
  uint64_t ans = -UINT64_C(1);
  if (scanf("%d%d", &N, &M) != 2) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d", &C[i]) != 1) return 1;
  }
  for (i = 0; i < M; i++) {
    if (scanf("%d", &K[i]) != 1) return 1;
    for (j = 0; j < K[i]; j++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int N, M;
int C[16];
int K[128];
int A[128][16];

uint64_t target[2];
uint64_t offer[128][2];

int main(void) {
	int i, j;
	uint64_t ans = -UINT64_C(1);
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &C[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%d", &K[i]) != 1) return 1;
		for (j = 0; j < K[i]; j++) {
			if (scanf("%d", &A[i][j]) != 1) return 1;
			offer[A[i][j] - 1][i / 64] |= UINT64_C(1) << (i % 64);
		}
	}
	if (M < 64) {
		target[0] = (UINT64_C(1) << M) - 1;
		target[1] = 0;
	} else {
		target[0] = -UINT64_C(1);
		target[1] = (UINT64_C(1) << (M - 64)) - 1;
	}
	for (i = 0; i < (1 << (N * 2)); i++) {
		uint64_t cost = 0;
		uint64_t seen1[2] = {0, 0}, seen2[2] = {0, 0};
		for (j = 0; j < N * 2; j++) {
			if ((i >> j) & 1) {
				cost += C[j / 2];
				seen2[0] |= offer[j / 2][0] & seen1[0];
				seen2[1] |= offer[j / 2][1] & seen1[1];
				seen1[0] |= offer[j / 2][0];
				seen1[1] |= offer[j / 2][1];
			}
		}
		if (seen2[0] == target[0] && seen2[1] == target[1] && cost < ans) {
			ans = cost;
		}
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

Submission Info

Submission Time	2025-05-29 06:47:52
Task	D - Goin' to the Zoo
User	mikecat
Language	C (gcc 12.2.0)
Score	400
Code Size	1211 Byte
Status	AC
Exec Time	69 ms
Memory	1736 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 2

× 35

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt
All	hand_01.txt, hand_02.txt, hand_03.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt

Case Name	Status	Exec Time	Memory
hand_01.txt	AC	1 ms	1628 KiB
hand_02.txt	AC	0 ms	1732 KiB
hand_03.txt	AC	0 ms	1720 KiB
random_01.txt	AC	68 ms	1628 KiB
random_02.txt	AC	69 ms	1616 KiB
random_03.txt	AC	66 ms	1628 KiB
random_04.txt	AC	67 ms	1736 KiB
random_05.txt	AC	69 ms	1612 KiB
random_06.txt	AC	16 ms	1712 KiB
random_07.txt	AC	66 ms	1708 KiB
random_08.txt	AC	1 ms	1720 KiB
random_09.txt	AC	68 ms	1724 KiB
random_10.txt	AC	0 ms	1612 KiB
random_11.txt	AC	67 ms	1708 KiB
random_12.txt	AC	0 ms	1576 KiB
random_13.txt	AC	68 ms	1712 KiB
random_14.txt	AC	1 ms	1720 KiB
random_15.txt	AC	66 ms	1724 KiB
random_16.txt	AC	0 ms	1624 KiB
random_17.txt	AC	68 ms	1584 KiB
random_18.txt	AC	0 ms	1728 KiB
random_19.txt	AC	67 ms	1576 KiB
random_20.txt	AC	69 ms	1704 KiB
random_21.txt	AC	1 ms	1688 KiB
random_22.txt	AC	67 ms	1568 KiB
random_23.txt	AC	1 ms	1624 KiB
random_24.txt	AC	17 ms	1616 KiB
random_25.txt	AC	1 ms	1712 KiB
random_26.txt	AC	67 ms	1632 KiB
random_27.txt	AC	1 ms	1620 KiB
random_28.txt	AC	4 ms	1608 KiB
random_29.txt	AC	4 ms	1716 KiB
random_30.txt	AC	16 ms	1612 KiB
sample_01.txt	AC	0 ms	1704 KiB
sample_02.txt	AC	1 ms	1628 KiB