結果

問題 No.225 文字列変更(medium)
コンテスト
ユーザー bal4u
提出日時 2019-04-14 15:30:12
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,072 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 30,720 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 01:49:57
合計ジャッジ時間 1,061 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: note: in expansion of macro 'gc'
   14 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.225 文字列変更(medium)
// 2019.4.14 bal4u

#include <stdio.h>

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()   // 整数の入力（負数に対応）
{
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void ins(char *s)  // 文字列の入力　スペース以下の文字で入力終了
{
	do *s = gc();
	while (*s++ > ' ');
	*(s - 1) = 0;
}

int M[1005][1005];

int LCS(char *str1, int len1, char *str2, int len2)
{
	int  i, j;

	for (j = 0; j <= len1; j++) M[j][0] = j;
	for (i = 0; i <= len2; i++) M[0][i] = i;
	for (j = 1; j <= len1; j++) {
		for (i = 1; i <= len2; i++) {
			int d, min;
			d = (str1[j - 1] != str2[i - 1]);
			min = M[j - 1][i] + 1;
			if (min > M[j][i - 1] + 1) min = M[j][i - 1] + 1;
			if (min > M[j - 1][i - 1] + d) min = M[j - 1][i - 1] + d;
			M[j][i] = min;
		}
	}
	return M[len1][len2];
}

int n, m;
char S[1005], T[1005];

int main()
{
	n = in(), m = in();
	ins(S), ins(T);
	printf("%d\n", LCS(S, n, T, m));
	return 0;
}
0