Submission #4035052


Source Code Expand

from copy import deepcopy
n,k = map(int,input().split())
a = list(map(int,input().split()))
migi = []
hidari = []
dp2 = [float("inf")]*n
matome = set()
matome.add(0)
hidari.append(deepcopy(matome))
for i in range(1,n):
  for j in list(matome):
    if j + a[i-1] < k:
      matome.add(j + a[i-1])
  hidari.append(deepcopy(matome))
matome = set()
matome.add(0)
migi.append(deepcopy(matome))
for i in range(n-2,-1,-1):
  for j in list(matome):
    if j + a[i+1] < k:
      matome.add(j + a[i+1])
  migi.append(deepcopy(matome))
migi = migi[::-1]
for i in range(n):
  m = list(migi[i])
  h = list(hidari[i])
  m.sort()
  h.sort()
  now = len(h)-1
  for j in m:
    while True:
      if h[now] + j+a[i] >= k:
        dp2[i] = min(dp2[i],h[now]+j+a[i])
        if now == 0:
          break
        if h[now-1] + j+a[i] >= k:
          now -=1
        else:
          break
      else:
        break
ans = 0
for i in range(n):
  if dp2[i] - a[i] >= k:
    ans += 1
print(ans)

Submission Info

Submission Time
Task D - No Need
User rookzeno
Language PyPy3 (2.4.0)
Score 300
Code Size 1013 Byte
Status TLE
Exec Time 2129 ms
Memory 395912 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 0 / 300
Status
AC × 3
AC × 26
AC × 37
TLE × 14
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
Subtask 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
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, 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, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt
Case Name Status Exec Time Memory
0_000.txt AC 189 ms 38512 KB
0_001.txt AC 173 ms 38256 KB
0_002.txt AC 176 ms 38256 KB
1_003.txt AC 179 ms 38256 KB
1_004.txt AC 174 ms 38256 KB
1_005.txt AC 178 ms 38256 KB
1_006.txt AC 202 ms 40560 KB
1_007.txt AC 203 ms 40560 KB
1_008.txt AC 376 ms 56924 KB
1_009.txt AC 364 ms 56412 KB
1_010.txt AC 230 ms 40304 KB
1_011.txt AC 231 ms 40304 KB
1_012.txt AC 228 ms 40304 KB
1_013.txt AC 228 ms 40304 KB
1_014.txt AC 248 ms 40304 KB
1_015.txt AC 454 ms 72796 KB
1_016.txt AC 176 ms 38256 KB
1_017.txt AC 185 ms 38256 KB
1_018.txt AC 177 ms 38256 KB
1_019.txt AC 328 ms 50780 KB
1_020.txt AC 316 ms 47964 KB
1_021.txt AC 361 ms 54748 KB
1_022.txt AC 304 ms 49884 KB
1_023.txt AC 257 ms 44784 KB
1_024.txt AC 334 ms 52060 KB
1_025.txt AC 347 ms 53340 KB
2_026.txt AC 174 ms 38256 KB
2_027.txt AC 202 ms 40688 KB
2_028.txt AC 218 ms 40688 KB
2_029.txt TLE 2123 ms 308488 KB
2_030.txt TLE 2124 ms 311176 KB
2_031.txt AC 490 ms 52312 KB
2_032.txt AC 496 ms 52440 KB
2_033.txt AC 486 ms 52184 KB
2_034.txt AC 493 ms 52184 KB
2_035.txt AC 494 ms 52312 KB
2_036.txt TLE 2121 ms 204936 KB
2_037.txt AC 209 ms 41712 KB
2_038.txt AC 206 ms 41456 KB
2_039.txt AC 205 ms 42096 KB
2_040.txt TLE 2118 ms 217732 KB
2_041.txt TLE 2122 ms 294024 KB
2_042.txt TLE 2119 ms 236680 KB
2_043.txt TLE 2118 ms 225928 KB
2_044.txt TLE 2120 ms 267548 KB
2_045.txt TLE 2129 ms 395912 KB
2_046.txt TLE 2124 ms 318600 KB
2_047.txt TLE 2124 ms 325384 KB
2_048.txt TLE 2123 ms 307336 KB
2_049.txt TLE 2124 ms 317576 KB
2_050.txt TLE 2123 ms 310024 KB