Submission #8314263
Source Code Expand
from itertools import accumulate n = int(input()) b = [] # iがあるインデックス bc = {} wc = {} for i in range(2*n): c,a = input().split() a = int(a) b.append((c,a)) if c == "B": bc[a]=i else: wc[a]=i # black[i][j] : 黒のi(1-indexed)のある位置より左にある、i未満の個数 + 白のj以下の個数 black = [[0]*(n+1) for i in range(n+1)] white = [[0]*(n+1) for i in range(n+1)] for i in range(2*n): c,a = b[i] # 同色でa未満の個数 cnt cnt = 0 num = [0]*(n+1) for j in range(i): if b[j][0] == c: if b[j][1] < a: cnt += 1 else: num[b[j][1]] += 1 # 累積和 num = list(accumulate(num)) if c == "B": black[a] = [j+cnt for j in num] else: white[a] = [j+cnt for j in num] DP = [[float("inf")]*(n+1) for i in range(n+1)] DP[0][0] = 0 for i in range(n+1): for j in range(n+1): # 黒がi個、白がj個→i+1, j or i, j+1 if i+1 <= n: DP[i+1][j] = min(DP[i+1][j], DP[i][j]+bc[i+1]-black[i+1][j]) if j+1 <= n: DP[i][j+1] = min(DP[i][j+1], DP[i][j]+wc[j+1]-white[j+1][i]) print(DP[n][n])
Submission Info
Submission Time | |
---|---|
Task | E - Sorted and Sorted |
User | tomboftime |
Language | PyPy3 (2.4.0) |
Score | 600 |
Code Size | 1255 Byte |
Status | AC |
Exec Time | 1382 ms |
Memory | 212228 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_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, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 160 ms | 38256 KB |
0_001.txt | AC | 160 ms | 38256 KB |
0_002.txt | AC | 161 ms | 38256 KB |
1_003.txt | AC | 159 ms | 38256 KB |
1_004.txt | AC | 160 ms | 38256 KB |
1_005.txt | AC | 161 ms | 38256 KB |
1_006.txt | AC | 162 ms | 38256 KB |
1_007.txt | AC | 160 ms | 38256 KB |
1_008.txt | AC | 163 ms | 38256 KB |
1_009.txt | AC | 164 ms | 38256 KB |
1_010.txt | AC | 159 ms | 38256 KB |
1_011.txt | AC | 160 ms | 38384 KB |
1_012.txt | AC | 158 ms | 38256 KB |
1_013.txt | AC | 159 ms | 38256 KB |
1_014.txt | AC | 1151 ms | 187908 KB |
1_015.txt | AC | 401 ms | 77912 KB |
1_016.txt | AC | 926 ms | 143492 KB |
1_017.txt | AC | 528 ms | 110040 KB |
1_018.txt | AC | 197 ms | 41200 KB |
1_019.txt | AC | 354 ms | 67800 KB |
1_020.txt | AC | 1018 ms | 167044 KB |
1_021.txt | AC | 514 ms | 117464 KB |
1_022.txt | AC | 397 ms | 83928 KB |
1_023.txt | AC | 838 ms | 143108 KB |
1_024.txt | AC | 1184 ms | 199172 KB |
1_025.txt | AC | 1360 ms | 208772 KB |
1_026.txt | AC | 1361 ms | 211588 KB |
1_027.txt | AC | 1361 ms | 209540 KB |
1_028.txt | AC | 1373 ms | 212100 KB |
1_029.txt | AC | 1374 ms | 211844 KB |
1_030.txt | AC | 1362 ms | 209540 KB |
1_031.txt | AC | 1382 ms | 212228 KB |
1_032.txt | AC | 1199 ms | 201476 KB |
1_033.txt | AC | 1183 ms | 201476 KB |
1_034.txt | AC | 1231 ms | 201476 KB |
1_035.txt | AC | 1209 ms | 202116 KB |