Submission #44971542

Source Code Expand

n=int(input())
area=[]
for _ in range(n):
  x=list(map(int,input().split()))
  area.append(x)
  
dp = [[1<<60 for _ in range(100001)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
  negaeri=0
  if area[i][0] < area[i][1]:
    negaeri = (area[i][0] + area[i][1])//2 + 1 - area[i][0]
  for j in range(100001):
    dp[i+1][j] = min(dp[i][j],dp[i+1][j])
    if j + area[i][2] > 100000:
      continue
    dp[i+1][j+area[i][2]] = min(dp[i][j] + negaeri, dp[i+1][j+area[i][2]])
ans=1<<60
z=0
for i in range(n):
  z+=area[i][2]
for i in range(z//2+1,100001):
  ans=min(ans,dp[n][i])
print(ans)

Submission Info

Submission Time
Task D - President
User gootara
Language Python (PyPy 3.10-v7.3.12)
Score 400
Code Size 618 Byte
Status AC
Exec Time 324 ms
Memory 161352 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 31
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 02_max_00.txt, 03_hack_00.txt, 03_hack_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 64 ms 82628 KiB
00_sample_01.txt AC 67 ms 83660 KiB
00_sample_02.txt AC 72 ms 84308 KiB
00_sample_03.txt AC 91 ms 90176 KiB
01_random_00.txt AC 157 ms 110764 KiB
01_random_01.txt AC 256 ms 160956 KiB
01_random_02.txt AC 290 ms 160992 KiB
01_random_03.txt AC 276 ms 153148 KiB
01_random_04.txt AC 316 ms 161116 KiB
01_random_05.txt AC 275 ms 161132 KiB
01_random_06.txt AC 159 ms 113344 KiB
01_random_07.txt AC 311 ms 161312 KiB
01_random_08.txt AC 298 ms 161048 KiB
01_random_09.txt AC 260 ms 160224 KiB
01_random_10.txt AC 303 ms 161280 KiB
01_random_11.txt AC 282 ms 161180 KiB
01_random_12.txt AC 237 ms 136976 KiB
01_random_13.txt AC 253 ms 160956 KiB
01_random_14.txt AC 290 ms 161304 KiB
01_random_15.txt AC 84 ms 89388 KiB
01_random_16.txt AC 302 ms 161112 KiB
01_random_17.txt AC 301 ms 161352 KiB
01_random_18.txt AC 287 ms 155684 KiB
01_random_19.txt AC 298 ms 161252 KiB
01_random_20.txt AC 304 ms 161236 KiB
01_random_21.txt AC 304 ms 161044 KiB
01_random_22.txt AC 324 ms 161292 KiB
01_random_23.txt AC 255 ms 161244 KiB
02_max_00.txt AC 248 ms 160688 KiB
03_hack_00.txt AC 249 ms 160652 KiB
03_hack_01.txt AC 279 ms 161204 KiB