結果
問題 | No.798 コレクション |
ユーザー |
![]() |
提出日時 | 2019-03-15 22:34:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 555 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 81,808 KB |
実行使用メモリ | 77,076 KB |
最終ジャッジ日時 | 2024-07-01 21:14:08 |
合計ジャッジ時間 | 2,942 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
N=int(input()) P=[list(map(int,input().split())) for i in range(N)] P.sort(key=lambda x:x[0]) P.sort(key=lambda x:x[1],reverse=True) DP=[P[i][0] for i in range(N)] for i in range(1,N): if DP[i]>DP[i-1]: DP[i]=DP[i-1] #print(DP) if N%3==0: days=N*2//3 elif N%3==1: days=(N-1)*2//3+1 else: days=(N+1)*2//3 for i in range(1,days): NDP=[10**15]*N for j in range(1,N): NDP[j]=min(DP[j-1]+(P[j][0]+P[j][1]*i),NDP[j-1]) #print(DP[j-1]+(P[j][0]+P[j][1]*i),NDP[j-1]) DP=NDP #print(DP) print(min(DP))