結果

問題 No.3583 二部マッチング最適化
コンテスト
ユーザー ゼット
提出日時 2026-07-04 01:51:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 3,338 ms / 6,000 ms
コード長 776 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 677 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 96,384 KB
最終ジャッジ日時 2026-07-04 01:52:25
合計ジャッジ時間 19,853 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N,M,L=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
va=[0]*3000
vb=[0]*3000
count=0
for x in A:
  va[x]+=1
for x in B:
  vb[x]+=1
A=[]
B=[]
for x in range(-1000,1001):
  z=min(va[x],vb[x])
  count+=z
  for i in range(va[x]-z):
    A.append(x)
  for i in range(vb[x]-z):
    B.append(x)
N=len(A)
M=len(B)
L-=count
if L<=0:
  print(0)
  exit()
dp=[10**10]*((L+1)*(N+1))
v=[10**10]*((L+1)*(N+1))
dp[0]=0
for j in range(N+1):
  v[j]=0
for i in range(M):
  x=B[i]
  for count in range(i+1,0,-1):
    if count>L:
      continue
    for j in range(count,N+1):
      y=A[j-1]
      dp[count*(N+1)+j]=min(dp[count*(N+1)+j],v[(count-1)*(N+1)+j-1]+abs(x-y))
      v[count*(N+1)+j]=min(v[count*(N+1)+j-1],dp[count*(N+1)+j])
print(v[L*(N+1)+N])
0