(cache)Submission #76357576 - AtCoder Beginner Contest 452

Contest Duration: 2026-04-04(Sat) 21:00 - 2026-04-04(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #76357576

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
#include <stdio.h>
#include <inttypes.h>
char S[212345];
char T[64];
int64_t memo[212345][64][2];
int64_t calc(int pos, int tpos, int running) {
  int64_t ans = running; /* running → この直前までで終わるパターンを数える */
  if (T[tpos] == '\0') return 0;
  if (S[pos] == '\0') return ans;
  if (memo[pos][tpos][running]) return ~memo[pos][tpos][running];
  /* 入れない */
  if (!running) {
    ans += calc(pos + 1, tpos, 0);
  }
  /* 入れる */
  ans += calc(pos + 1, tpos + (S[pos] == T[tpos]), 1);
  return ~(memo[pos][tpos][running] = ~ans);
}
int main(void) {
  if (scanf("%212344s", S) != 1) return 1;
  if (scanf("%63s", T) != 1) return 1;
  printf("%" PRId64 "\n", calc(0, 0, 0));
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

char S[212345];
char T[64];

int64_t memo[212345][64][2];

int64_t calc(int pos, int tpos, int running) {
	int64_t ans = running; /* running → この直前までで終わるパターンを数える */
	if (T[tpos] == '\0') return 0;
	if (S[pos] == '\0') return ans;
	if (memo[pos][tpos][running]) return ~memo[pos][tpos][running];
	/* 入れない */
	if (!running) {
		ans += calc(pos + 1, tpos, 0);
	}
	/* 入れる */
	ans += calc(pos + 1, tpos + (S[pos] == T[tpos]), 1);
	return ~(memo[pos][tpos][running] = ~ans);
}

int main(void) {
	if (scanf("%212344s", S) != 1) return 1;
	if (scanf("%63s", T) != 1) return 1;
	printf("%" PRId64 "\n", calc(0, 0, 0));
	return 0;
}

Submission Info

Submission Time	2026-06-03 07:26:19
Task	D - No-Subsequence Substring
User	mikecat
Language	C23 (GCC 14.2.0)
Score	400
Code Size	745 Byte
Status	AC
Exec Time	143 ms
Memory	217508 KiB

Judge Result

Set Name

Sample

All

after_contest

Score / Max Score

0 / 0

400 / 400

0 / 0

Status

× 3

× 56

× 2

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.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, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt
after_contest	02_after_contest_56.txt, 02_after_contest_57.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	0 ms	1496 KiB
00_sample_01.txt	AC	0 ms	1620 KiB
00_sample_02.txt	AC	0 ms	1828 KiB
01_random_03.txt	AC	72 ms	135068 KiB
01_random_04.txt	AC	77 ms	142424 KiB
01_random_05.txt	AC	40 ms	78500 KiB
01_random_06.txt	AC	40 ms	73892 KiB
01_random_07.txt	AC	58 ms	112844 KiB
01_random_08.txt	AC	114 ms	217420 KiB
01_random_09.txt	AC	117 ms	217500 KiB
01_random_10.txt	AC	115 ms	217508 KiB
01_random_11.txt	AC	119 ms	217304 KiB
01_random_12.txt	AC	112 ms	217304 KiB
01_random_13.txt	AC	114 ms	217420 KiB
01_random_14.txt	AC	116 ms	217244 KiB
01_random_15.txt	AC	116 ms	217508 KiB
01_random_16.txt	AC	118 ms	217432 KiB
01_random_17.txt	AC	116 ms	217384 KiB
01_random_18.txt	AC	112 ms	217384 KiB
01_random_19.txt	AC	119 ms	217424 KiB
01_random_20.txt	AC	116 ms	217412 KiB
01_random_21.txt	AC	114 ms	217508 KiB
01_random_22.txt	AC	118 ms	217384 KiB
01_random_23.txt	AC	118 ms	217428 KiB
01_random_24.txt	AC	117 ms	217408 KiB
01_random_25.txt	AC	123 ms	217508 KiB
01_random_26.txt	AC	116 ms	217384 KiB
01_random_27.txt	AC	115 ms	217412 KiB
01_random_28.txt	AC	115 ms	217412 KiB
01_random_29.txt	AC	113 ms	217500 KiB
01_random_30.txt	AC	113 ms	217244 KiB
01_random_31.txt	AC	113 ms	217420 KiB
01_random_32.txt	AC	111 ms	217424 KiB
01_random_33.txt	AC	117 ms	217384 KiB
01_random_34.txt	AC	117 ms	217408 KiB
01_random_35.txt	AC	117 ms	217432 KiB
01_random_36.txt	AC	118 ms	217508 KiB
01_random_37.txt	AC	115 ms	217412 KiB
01_random_38.txt	AC	115 ms	217428 KiB
01_random_39.txt	AC	115 ms	217508 KiB
01_random_40.txt	AC	100 ms	195012 KiB
01_random_41.txt	AC	87 ms	172868 KiB
01_random_42.txt	AC	98 ms	187172 KiB
01_random_43.txt	AC	34 ms	68036 KiB
01_random_44.txt	AC	81 ms	158144 KiB
01_random_45.txt	AC	21 ms	40516 KiB
01_random_46.txt	AC	96 ms	187200 KiB
01_random_47.txt	AC	52 ms	103248 KiB
01_random_48.txt	AC	35 ms	68952 KiB
01_random_49.txt	AC	89 ms	143172 KiB
01_random_50.txt	AC	97 ms	179800 KiB
01_random_51.txt	AC	142 ms	217304 KiB
01_random_52.txt	AC	109 ms	217408 KiB
01_random_53.txt	AC	0 ms	1616 KiB
01_random_54.txt	AC	0 ms	1604 KiB
01_random_55.txt	AC	0 ms	1600 KiB
02_after_contest_56.txt	AC	143 ms	217412 KiB
02_after_contest_57.txt	AC	110 ms	217384 KiB