(cache)Submission #71214774 - いろはちゃんコンテスト Day2

Contest Duration: 2019-05-01(Wed) 13:00 - 2019-05-01(Wed) 18:00 (local time) (300 minutes) Back to Home

Submission #71214774

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>
char S[5123];
char T[5123];
int ans[5123][5123];
int main(void) {
  int i, j;
  if (scanf("%5121s", S + 1) != 1) return 1;
  if (scanf("%5121s", T + 1) != 1) return 1;
  for (i = 1; i == 1 || S[i - 1] != '\0'; i++) {
    for (j = 1; j == 1 || T[j - 1] != '\0'; j++) {
      int curans = ans[i - 1][j];
      if (ans[i][j - 1] > curans) curans = ans[i][j - 1];
      if (S[i - 1] != '\0' && S[i - 1] == T[j - 1]) {
        if (ans[i - 1][j - 1] + 1 > curans) curans = ans[i - 1][j - 1] + 1;
      }
      ans[i][j] = curans;
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

char S[5123];
char T[5123];

int ans[5123][5123];

int main(void) {
	int i, j;
	if (scanf("%5121s", S + 1) != 1) return 1;
	if (scanf("%5121s", T + 1) != 1) return 1;
	for (i = 1; i == 1 || S[i - 1] != '\0'; i++) {
		for (j = 1; j == 1 || T[j - 1] != '\0'; j++) {
			int curans = ans[i - 1][j];
			if (ans[i][j - 1] > curans) curans = ans[i][j - 1];
			if (S[i - 1] != '\0' && S[i - 1] == T[j - 1]) {
				if (ans[i - 1][j - 1] + 1 > curans) curans = ans[i - 1][j - 1] + 1;
			}
			ans[i][j] = curans;
		}
	}
	printf("%d\n", ans[i - 1][j - 1] + 1);
	return 0;
}

/*

最長共通部分列の長さを求め、+1

行動の選択肢
・Sの注目位置を1進める
・Tの注目位置を1進める
・両方の注目位置を1進め、スコアを1増やす (マッチしている場合のみ)

*/

Submission Info

Submission Time	2025-11-25 07:20:49
Task	A - わたのはら
User	mikecat
Language	C (gcc 12.2.0)
Score	300
Code Size	852 Byte
Status	AC
Exec Time	85 ms
Memory	101664 KiB

Judge Result

Set Name

Sample

Subtask1

Score / Max Score

0 / 0

300 / 300

Status

× 2

× 16

Set Name	Test Cases
Sample	sample_1.txt, sample_2.txt
Subtask1	sample_1.txt, sample_2.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, large_1.txt, large_2.txt, large_3.txt, large_4.txt, large_5.txt, large_6.txt, large_7.txt

Case Name	Status	Exec Time	Memory
large_1.txt	AC	23 ms	31208 KiB
large_2.txt	AC	32 ms	43204 KiB
large_3.txt	AC	37 ms	48908 KiB
large_4.txt	AC	49 ms	63372 KiB
large_5.txt	AC	29 ms	39508 KiB
large_6.txt	AC	65 ms	83816 KiB
large_7.txt	AC	85 ms	101664 KiB
sample_1.txt	AC	0 ms	1720 KiB
sample_2.txt	AC	0 ms	1748 KiB
small_1.txt	AC	1 ms	2168 KiB
small_2.txt	AC	2 ms	4264 KiB
small_3.txt	AC	2 ms	4320 KiB
small_4.txt	AC	4 ms	6568 KiB
small_5.txt	AC	1 ms	3196 KiB
small_6.txt	AC	1 ms	3600 KiB
small_7.txt	AC	1 ms	2772 KiB