提出 #72904852

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//const int mod=;

int t, n, c;
int a[3005][3005];
int h[3005];
int dp[3005][3005][2];

void solve() {
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		h[i] = 0;
	for (int i = 1; i <= n; i++)
		for (int k = 1; k <= n; k++)
			for (int j = 0; j < 2; j++)
				dp[i][k][j] = 0;
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= n; k++) {
			a[i][k]=0;
			char f;
			cin >> f;
			if (f == '#') h[k] = max(h[k], i), a[i][k] = 1;
		}
	}
	dp[n][c][0] = dp[n][c][1] = 1;
	for (int i = n - 1; i >= 1; i--) {
		for (int k = 1; k <= n; k++) {
			for (int j = k - 1; j <= k + 1; j++)
				dp[i][k][0] |= dp[i + 1][k][1] | (dp[i + 1][j][0] & ((1 - a[i][k]) | (i == h[k] ? 1 : 0)));
			for (int j = k - 1; j <= k + 1; j++)
				dp[i][k][1] |= dp[i + 1][k][1] | (dp[i + 1][j][0] & (i >= h[k] ? 1 : 0));
		}
	}
//	for (int i=1;i<=n;i++,cout<<endl)
//		for (int k=1;k<=n;k++)
//			cout<<dp[i][k][0]<<" ";
	for (int i = 1; i <= n; i++)
		cout << dp[1][i][0];
	cout << endl;
	return;
}

signed main() {

	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);

	cin >> t;
	while (t--)solve();

	return 0;
}

提出情報

提出日時
問題 E - Climbing Silver
ユーザ KDL_ANIPLEX
言語 C++23 (Clang 21.1.0)
得点 450
コード長 1215 Byte
結果 AC
実行時間 658 ms
メモリ 108652 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 450 / 450
結果
AC × 1
AC × 48
セット名 テストケース
Sample sample_01.txt
All sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 1 ms 2932 KiB
test_01.txt AC 62 ms 2872 KiB
test_02.txt AC 83 ms 2804 KiB
test_03.txt AC 113 ms 2872 KiB
test_04.txt AC 143 ms 3016 KiB
test_05.txt AC 182 ms 3040 KiB
test_06.txt AC 228 ms 2984 KiB
test_07.txt AC 276 ms 2892 KiB
test_08.txt AC 334 ms 3016 KiB
test_09.txt AC 404 ms 3016 KiB
test_10.txt AC 471 ms 2996 KiB
test_11.txt AC 554 ms 2948 KiB
test_12.txt AC 628 ms 2996 KiB
test_13.txt AC 658 ms 3036 KiB
test_14.txt AC 594 ms 3168 KiB
test_15.txt AC 564 ms 6260 KiB
test_16.txt AC 565 ms 6380 KiB
test_17.txt AC 622 ms 108448 KiB
test_18.txt AC 608 ms 108636 KiB
test_19.txt AC 605 ms 108616 KiB
test_20.txt AC 619 ms 108616 KiB
test_21.txt AC 601 ms 108600 KiB
test_22.txt AC 613 ms 108500 KiB
test_23.txt AC 602 ms 108568 KiB
test_24.txt AC 606 ms 108640 KiB
test_25.txt AC 606 ms 108636 KiB
test_26.txt AC 596 ms 108540 KiB
test_27.txt AC 597 ms 108596 KiB
test_28.txt AC 601 ms 108600 KiB
test_29.txt AC 616 ms 108644 KiB
test_30.txt AC 621 ms 108492 KiB
test_31.txt AC 589 ms 108636 KiB
test_32.txt AC 622 ms 108592 KiB
test_33.txt AC 619 ms 108532 KiB
test_34.txt AC 634 ms 108520 KiB
test_35.txt AC 621 ms 108584 KiB
test_36.txt AC 616 ms 108652 KiB
test_37.txt AC 600 ms 108556 KiB
test_38.txt AC 602 ms 108636 KiB
test_39.txt AC 600 ms 108548 KiB
test_40.txt AC 617 ms 108640 KiB
test_41.txt AC 613 ms 108556 KiB
test_42.txt AC 594 ms 108616 KiB
test_43.txt AC 613 ms 108548 KiB
test_44.txt AC 608 ms 108584 KiB
test_45.txt AC 595 ms 108524 KiB
test_46.txt AC 605 ms 108500 KiB
test_47.txt AC 613 ms 108520 KiB