(cache)Submission #74720558 - AtCoder Beginner Contest 438

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

Submission #74720558

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <inttypes.h>
#define INF INT64_C(1010101010101010101)
int N;
int A[312345];
int B[312345];
int C[312345];
int64_t memo[312345][3];
int64_t calc(int pos, int status) {
  int64_t ans, candidate;
  if (pos >= N) return status == 2 ? 0 : -INF;
  if (memo[pos][status]) return ~memo[pos][status];
  if (status == 0) {
    ans = calc(pos + 1, 0) + A[pos];
    if (pos > 0) {
      candidate = calc(pos + 1, 1) + B[pos];
      if (candidate > ans) ans = candidate;
    }
  } else if (status == 1) {
    ans = calc(pos + 1, 1) + B[pos];
    candidate = calc(pos + 1, 2) + C[pos];
    if (candidate > ans) ans = candidate;
  } else {
    ans = calc(pos + 1, 2) + C[pos];
  }
  return ~(memo[pos][status] = ~ans);
}
int main(void) {
  int i;
  if (scanf("%d", &N) != 1) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d", &A[i]) != 1) return 1;
  }
  for (i = 0; i < N; i++) {
    if (scanf("%d", &B[i]) != 1) return 1;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define INF INT64_C(1010101010101010101)

int N;
int A[312345];
int B[312345];
int C[312345];

int64_t memo[312345][3];

int64_t calc(int pos, int status) {
	int64_t ans, candidate;
	if (pos >= N) return status == 2 ? 0 : -INF;
	if (memo[pos][status]) return ~memo[pos][status];
	if (status == 0) {
		ans = calc(pos + 1, 0) + A[pos];
		if (pos > 0) {
			candidate = calc(pos + 1, 1) + B[pos];
			if (candidate > ans) ans = candidate;
		}
	} else if (status == 1) {
		ans = calc(pos + 1, 1) + B[pos];
		candidate = calc(pos + 1, 2) + C[pos];
		if (candidate > ans) ans = candidate;
	} else {
		ans = calc(pos + 1, 2) + C[pos];
	}
	return ~(memo[pos][status] = ~ans);
}

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

Submission Info

Submission Time	2026-04-06 01:29:57
Task	D - Tail of Snake
User	mikecat
Language	C23 (GCC 14.2.0)
Score	400
Code Size	1084 Byte
Status	AC
Exec Time	67 ms
Memory	31068 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 3

× 38

Set Name	Test Cases
Sample	sample00.txt, sample01.txt, sample02.txt
All	sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt

Case Name	Status	Exec Time	Memory
sample00.txt	AC	0 ms	1568 KiB
sample01.txt	AC	1 ms	1556 KiB
sample02.txt	AC	0 ms	1652 KiB
testcase00.txt	AC	0 ms	1616 KiB
testcase01.txt	AC	0 ms	1636 KiB
testcase02.txt	AC	1 ms	1616 KiB
testcase03.txt	AC	60 ms	31044 KiB
testcase04.txt	AC	59 ms	30928 KiB
testcase05.txt	AC	59 ms	30928 KiB
testcase06.txt	AC	58 ms	30952 KiB
testcase07.txt	AC	59 ms	30828 KiB
testcase08.txt	AC	59 ms	30928 KiB
testcase09.txt	AC	60 ms	30932 KiB
testcase10.txt	AC	60 ms	30964 KiB
testcase11.txt	AC	60 ms	30948 KiB
testcase12.txt	AC	58 ms	30952 KiB
testcase13.txt	AC	58 ms	30928 KiB
testcase14.txt	AC	59 ms	30880 KiB
testcase15.txt	AC	55 ms	31036 KiB
testcase16.txt	AC	55 ms	30828 KiB
testcase17.txt	AC	21 ms	11216 KiB
testcase18.txt	AC	56 ms	27676 KiB
testcase19.txt	AC	63 ms	31068 KiB
testcase20.txt	AC	44 ms	22172 KiB
testcase21.txt	AC	36 ms	18756 KiB
testcase22.txt	AC	62 ms	31004 KiB
testcase23.txt	AC	9 ms	5976 KiB
testcase24.txt	AC	46 ms	23080 KiB
testcase25.txt	AC	64 ms	31068 KiB
testcase26.txt	AC	49 ms	22744 KiB
testcase27.txt	AC	59 ms	27932 KiB
testcase28.txt	AC	66 ms	30868 KiB
testcase29.txt	AC	45 ms	21416 KiB
testcase30.txt	AC	47 ms	22480 KiB
testcase31.txt	AC	66 ms	30828 KiB
testcase32.txt	AC	63 ms	29468 KiB
testcase33.txt	AC	54 ms	25536 KiB
testcase34.txt	AC	67 ms	30880 KiB