提出 #949122

ソースコード 拡げる

N,M=map(int,raw_input().split());C=[[0]*-~N for _ in range(N+1)];D=map(list,C);S=[raw_input()for _ in range(N)];r=0
for t in range(M-1):
	for i in range(1,N+1):
		for j in range(1,N+1):C[i][j]=C[i-1][j-1]+int(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N][N]
print r

提出情報

提出日時
問題 D - Friction
ユーザ leafmoon
言語 PyPy2 (5.6.0)
得点 800
コード長 298 Byte
結果 AC
実行時間 989 ms
メモリ 17648 KiB

ジャッジ結果

セット名 Sample Subtask All
得点 / 配点 0 / 0 300 / 300 500 / 500
結果
AC × 5
AC × 20
AC × 41
セット名 テストケース
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt
Subtask 0_000.txt, 0_001.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 2_023.txt, 2_024.txt, 2_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt
ケース名 結果 実行時間 メモリ
0_000.txt AC 38 ms 8944 KiB
0_001.txt AC 38 ms 8944 KiB
0_002.txt AC 37 ms 8944 KiB
0_003.txt AC 37 ms 8944 KiB
0_004.txt AC 40 ms 8944 KiB
1_005.txt AC 37 ms 8816 KiB
1_006.txt AC 122 ms 17648 KiB
1_007.txt AC 82 ms 13936 KiB
1_008.txt AC 79 ms 13936 KiB
1_009.txt AC 63 ms 12016 KiB
1_010.txt AC 91 ms 15472 KiB
1_011.txt AC 71 ms 12784 KiB
1_012.txt AC 72 ms 13040 KiB
1_013.txt AC 85 ms 14064 KiB
1_014.txt AC 93 ms 15472 KiB
1_015.txt AC 86 ms 14192 KiB
1_016.txt AC 96 ms 15472 KiB
1_017.txt AC 51 ms 9968 KiB
1_018.txt AC 90 ms 14960 KiB
1_019.txt AC 78 ms 13168 KiB
1_020.txt AC 83 ms 14320 KiB
1_021.txt AC 80 ms 13808 KiB
1_022.txt AC 81 ms 13680 KiB
2_023.txt AC 38 ms 8944 KiB
2_024.txt AC 968 ms 15856 KiB
2_025.txt AC 841 ms 14832 KiB
2_026.txt AC 577 ms 14832 KiB
2_027.txt AC 521 ms 12656 KiB
2_028.txt AC 774 ms 16112 KiB
2_029.txt AC 87 ms 11504 KiB
2_030.txt AC 760 ms 13680 KiB
2_031.txt AC 109 ms 13680 KiB
2_032.txt AC 989 ms 16112 KiB
2_033.txt AC 280 ms 14064 KiB
2_034.txt AC 948 ms 15856 KiB
2_035.txt AC 560 ms 15344 KiB
2_036.txt AC 915 ms 15856 KiB
2_037.txt AC 95 ms 13168 KiB
2_038.txt AC 842 ms 15600 KiB
2_039.txt AC 86 ms 12656 KiB
2_040.txt AC 836 ms 15216 KiB