結果

問題 No.3306 Life is Easy?
ユーザー sepa38
提出日時 2025-09-28 08:45:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,136 bytes
コンパイル時間 563 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 82,172 KB
最終ジャッジ日時 2025-09-28 08:45:49
合計ジャッジ時間 20,476 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def hungarian(n, c):
  w2j = list(range(n))
  j2w = list(range(n))
  p = [0] * n

  for i in range(1, n):
    cost = [1 << 60] * n
    prev = [-1] * n

    for j in range(i):
      cost[j2w[j]] = c[i][j] - c[j2w[j]][j] - p[j2w[j]]
      prev[j2w[j]] = i

    flg = [0] * n
    for j in range(i):
      min_c = 1 << 60
      cur_j = -1

      for k in range(i):
        if not flg[k] and min_c > cost[k]:
          min_c = cost[k]
          cur_j = k

      flg[cur_j] = 1

      for k in range(i):
        new_c = cost[cur_j] + c[cur_j][k] - c[j2w[k]][k] - (p[j2w[k]] - p[cur_j])
        if cost[j2w[k]] > new_c:
          cost[j2w[k]] = new_c
          prev[j2w[k]] = cur_j

    best_c = c[i][i]
    best_j = -1
    for j in range(i):
      if best_c > cost[j] + p[j] + c[j][i]:
        best_c = cost[j] + p[j] + c[j][i]
        best_j = j

    for j in range(i):
      p[j] += cost[j]
    
    next_i = i
    while best_j != -1:
      j2w[next_i] = best_j
      next_i, w2j[best_j] = w2j[best_j], next_i
      best_j = prev[best_j]

  return w2j


def solve(n, m, a):
  d = n // 2
  if m == 1:
    ans = 0
    for i in range(d):
      ans += a[~i][0] - a[i][0]
    return ans

  elif False:
    dp1 = [[1<<60] * (d + 1) for _ in range(d+1)]
    dp1[0][0] = 0
    for i in range(d):
      for j in range(i+1):
        dp1[i+1][j] = min(dp1[i+1][j], dp1[i][j]+a[i][0])
        dp1[i+1][j+1] = min(dp1[i+1][j+1], dp1[i][j]+a[i][1])

    dp2 = [[0] * (d + 1) for _ in range(d+1)]
    for i in range(d):
      for j in range(i+1):
        dp2[~i-1][j] = max(dp2[~i-1][j], dp2[~i][j]+a[~i][0])
        dp2[~i-1][j+1] = max(dp2[~i-1][j+1], dp2[~i][j]+a[~i][1])

    ans = 0
    for i in range(d+1):
      ans = max(ans, dp2[0][i]-dp1[d][i])
    return ans

  c = [[0] * d for _ in range(d)]
  for i in range(d):
    for j in range(d):
      x = 0
      for k in range(m):
        x = max(x, a[j+d+n%2][k] - a[i][k])
      c[i][j] = -x

  res = hungarian(d, c)
  ans = 0
  for i in range(d):
    ans -= c[i][res[i]]
  return ans

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

print(solve(n, m, a))
0