結果

問題 No.3427 Erasing a Subsequence
コンテスト
ユーザー pengin_2000
提出日時 2026-01-11 14:18:25
言語 C
(gcc 15.2.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 908 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,521 ms
コンパイル使用メモリ 39,816 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 14:18:27
合計ジャッジ時間 2,202 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
int s[1003], t[1003];
int right_id[1003];
int ans[1003], aa;
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	int i, j;
	for (i = 0; i < n; i++)
		scanf("%d", &s[i]);
	for (i = 0; i < m; i++)
		scanf("%d", &t[i]);
	right_id[n] = m;
	right_id[n + 1] = -1;
	for (j = m - 1, i = n - 1; i >= 0; i--)
	{
		if (j >= 0)
			if (s[i] == t[j])
				j--;
		right_id[i] = j;
	}
	int k, id, f;
	s[n] = 1e9;
	t[m] = 1e4;
	aa = 0;
	for (i = 0, j = 0; i < n; i++)
	{
		id = n;
		for (k = 0; i + k < n && j + k < m && s[i + k] == t[j + k]; k++)
		{
			if (s[id] > s[i + k] && right_id[i + k + 1] < j + k)
				id = i + k;
		}
		if (s[id] > s[i + k] && right_id[i + k + 1] <= j + k)
			id = i + k;
		if (id == n)
			break;
		ans[aa++] = s[id];
		k = id - i;
		i += k;
		j += k;
	}
	for (i = 0; i < aa - 1; i++)
		printf("%d ", ans[i]);
	if (aa > 0)
		printf("%d\n", ans[i]);
	else
		printf("\n");
	return 0;
}
0