(cache)Submission #70904063 - TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431)

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

Submission #70904063

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;
int W[512], H[512], B[512];
#define OFFSET (512 * 512)
#define INF INT64_C(101010101010101010)
int64_t memo[512 / 4][512 * 512 * 2];
int64_t calc(int pos, int diff) {
  int64_t ans, candidate;
  if (pos >= N) return diff >= 0 ? 0 : -INF;
  if (pos % 4 == 0 && memo[pos / 4][diff + OFFSET]) return ~memo[pos / 4][diff + OFFSET];
  /* 頭に取り付ける */
  ans = calc(pos + 1, diff - W[pos]) + H[pos];
  /* 体に取り付ける */
  candidate = calc(pos + 1, diff + W[pos]) + B[pos];
  if (candidate > ans) ans = candidate;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int N;
int W[512], H[512], B[512];

#define OFFSET (512 * 512)
#define INF INT64_C(101010101010101010)

int64_t memo[512 / 4][512 * 512 * 2];

int64_t calc(int pos, int diff) {
	int64_t ans, candidate;
	if (pos >= N) return diff >= 0 ? 0 : -INF;
	if (pos % 4 == 0 && memo[pos / 4][diff + OFFSET]) return ~memo[pos / 4][diff + OFFSET];

	/* 頭に取り付ける */
	ans = calc(pos + 1, diff - W[pos]) + H[pos];
	/* 体に取り付ける */
	candidate = calc(pos + 1, diff + W[pos]) + B[pos];
	if (candidate > ans) ans = candidate;

	if (pos % 4 == 0) memo[pos / 4][diff + OFFSET] = ~ans;
	return ans;
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d%d", &W[i], &H[i], &B[i]) != 3) return 1;
	}
	printf("%" PRId64 "\n", calc(0, 0));
	return 0;
}

Submission Info

Submission Time	2025-11-13 20:05:23
Task	D - Robot Customize
User	mikecat
Language	C23 (GCC 14.2.0)
Score	400
Code Size	883 Byte
Status	AC
Exec Time	776 ms
Memory	128752 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 4

× 54

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	1 ms	1624 KiB
00_sample_01.txt	AC	1 ms	1708 KiB
00_sample_02.txt	AC	0 ms	1792 KiB
00_sample_03.txt	AC	1 ms	1964 KiB
01_random_03.txt	AC	697 ms	119944 KiB
01_random_04.txt	AC	689 ms	119908 KiB
01_random_05.txt	AC	738 ms	127276 KiB
01_random_06.txt	AC	701 ms	123120 KiB
01_random_07.txt	AC	723 ms	124504 KiB
01_random_08.txt	AC	719 ms	124620 KiB
01_random_09.txt	AC	720 ms	124508 KiB
01_random_10.txt	AC	735 ms	127692 KiB
01_random_11.txt	AC	733 ms	125900 KiB
01_random_12.txt	AC	431 ms	77532 KiB
01_random_13.txt	AC	149 ms	28620 KiB
01_random_14.txt	AC	125 ms	23572 KiB
01_random_15.txt	AC	244 ms	45532 KiB
01_random_16.txt	AC	81 ms	16216 KiB
01_random_17.txt	AC	711 ms	123724 KiB
01_random_18.txt	AC	738 ms	127068 KiB
01_random_19.txt	AC	719 ms	125024 KiB
01_random_20.txt	AC	684 ms	119244 KiB
01_random_21.txt	AC	700 ms	123028 KiB
01_random_22.txt	AC	126 ms	24676 KiB
01_random_23.txt	AC	1 ms	2124 KiB
01_random_24.txt	AC	0 ms	1724 KiB
01_random_25.txt	AC	710 ms	121344 KiB
01_random_26.txt	AC	776 ms	128752 KiB
01_random_27.txt	AC	735 ms	124364 KiB
01_random_28.txt	AC	743 ms	126124 KiB
01_random_29.txt	AC	757 ms	127532 KiB
01_random_30.txt	AC	763 ms	126796 KiB
01_random_31.txt	AC	517 ms	90584 KiB
01_random_32.txt	AC	244 ms	45192 KiB
01_random_33.txt	AC	0 ms	1672 KiB
01_random_34.txt	AC	0 ms	1632 KiB
01_random_35.txt	AC	718 ms	124620 KiB
01_random_36.txt	AC	681 ms	118460 KiB
01_random_37.txt	AC	722 ms	125536 KiB
01_random_38.txt	AC	694 ms	120780 KiB
01_random_39.txt	AC	736 ms	127692 KiB
01_random_40.txt	AC	689 ms	120108 KiB
01_random_41.txt	AC	709 ms	122572 KiB
01_random_42.txt	AC	717 ms	124388 KiB
01_random_43.txt	AC	255 ms	47232 KiB
01_random_44.txt	AC	577 ms	102008 KiB
01_random_45.txt	AC	469 ms	83916 KiB
01_random_46.txt	AC	26 ms	6548 KiB
01_random_47.txt	AC	180 ms	33708 KiB
01_random_48.txt	AC	76 ms	126284 KiB
01_random_49.txt	AC	75 ms	126200 KiB
01_random_50.txt	AC	74 ms	126200 KiB
01_random_51.txt	AC	2 ms	3388 KiB
01_random_52.txt	AC	13 ms	22264 KiB