Problem:


シルクロード (Silk Road)

問題

現在カザフスタンがある地域には，古くは「シルクロード」と呼ばれる交易路があった．

シルクロード上には N + 1 個の都市があり，西から順に都市 0, 都市 1, ... , 都市 N と番号がつけられている．都市 i - 1 と都市 i の間の距離 (1 ≤ i ≤ N) は Di である．

貿易商である JOI 君は，都市 0 から出発して，都市を順番に経由し，都市 N まで絹を運ぶことになった．都市 0 から都市 N まで M 日以内に移動しなければならない．JOI 君は，それぞれの日の行動として，以下の 2 つのうちいずれか 1 つを選ぶ．

移動： 現在の都市から 1 つ東の都市へ 1 日かけて移動する．現在都市 i - 1 (1 ≤ i ≤ N) にいる場合は，都市 i に移動する．

待機： 移動を行わず，現在いる都市で 1 日待機する．

移動は大変であり，移動するたびに疲労度が溜まっていく．シルクロードでは日毎に天候の変動があり，天候が悪い日ほど移動には苦労を要する．

JOI 君が絹を運ぶのに使える M 日間のうち j 日目 (1 ≤ j ≤ M) の天候の悪さは Cj であることが分かっている．都市 i - 1 から都市 i (1 ≤ i ≤ N) に j 日目 (1 ≤ j ≤ M) に移動する場合，疲労度が Di &times; Cj だけ溜まってしまう．移動を行わず待機している日は疲労度は溜まらない．

JOI 君は，それぞれの日の行動をうまく選ぶことで，できるだけ疲労度を溜めずに移動したい．JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を求めよ．

入力

入力は 1 + N + M 行からなる．

1 行目には，2 つの整数 N, M (1 ≤ N ≤ M ≤ 1000) が空白を区切りとして書かれている．これは，シルクロードが N + 1 個の都市からなり，JOI 君が絹を都市 0 から都市 N まで M 日以内に運ばなければならないことを表す．

続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 Di (1 ≤ Di ≤ 1000) が書かれている．これは，都市 i - 1 と都市 i の間の距離が Di であることを表す．

続く M 行のうちの j 行目 (1 ≤ j ≤ M) には，整数 Cj (1 ≤ Cj ≤ 1000) が書かれている．これは，j 日目の天候の悪さが Cj であることを表す．

出力

JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を 1 行で出力せよ．

 入出力例

  
入力例 1

  

3 5
10
25
15
50
30
15
40
30

   
出力例 1

   

1125

  
入力例 2

  

2 6
99
20
490
612
515
131
931
1000

   
出力例 2

  

31589

入出力例 1 において，溜まる疲労度の合計を最小にするように JOI 君が移動するには次のようにする．

1 日目は待機する．

2 日目に都市 0 から都市 1 へ移動する．このとき溜まる疲労度は 10 &times; 30 = 300 である．

3 日目に都市 1 から都市 2 へ移動する．このとき溜まる疲労度は 25 &times; 15 = 375 である．

4 日目は待機する．

5 日目に都市 2 から都市 3 へ移動する．このとき溜まる疲労度は 15 &times; 30 = 450 である．

JOI 君がこのように移動した場合に溜まる疲労度の合計は 300 + 375 + 450 = 1125 である．これが最小値である．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 5
10
25
15
50
30
15
40
30


Sample output:
1125

Submission status: Wrong Answer

Solution code:

def sl(dn,cn):
    global f,tenkou,dist

    if dn>cn or dn<0:
        return False

    if f[dn][cn]==-1:
        a=sl(dn-1,cn-1)+dist[dn]*tenkou[cn]
        b=sl(dn,cn-1)
        c=min(a,b)
        f[dn][cn]=c
        return c
    else:
        return f[dn][cn]

#dn??\?????§???tenkou????????´???
def cost(dn,tenkou):
    global maxd,dist
    val=0
    for i in range(1,dn+1):
        print(i)
        val+=dist[i]*tenkou[i-1]
    return val

dd=input()
maxd,maxc=map(int,dd.split(" "))
dd=[int(input()) for i in range(maxd+maxc)]
dist=dd[:maxd]
dist.insert(0,0)
tenkou=dd[maxd:]
tenkou.insert(0,0)

f=[[-1 for j in range(maxc+1)]for i in range(maxd+1)]

for i in range(1,maxd+1):
    f[i][i]=cost(i,tenkou[1:i+1])

sl(maxd,maxc)

print(f[maxd][maxc])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(' '))
D = [int(input()) for i in range(N)]
C = [int(input()) for i in range(M)]

N += 1
dp = [[10 ** 10 for j in range(M)] for i in range(N)]
dp[0] = [0 for i in range(M)]

for town in range(1, N):
    for day in range(1, M):
        dp[town][day] = min(dp[town - 1][day - 1] + D[town - 1] * C[day], dp[town][day - 1])

print(min(dp[N - 1]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
d = [int(input()) for _ in range(n)]
c = [int(input()) for _ in range(m)]
h = [[10e10 for _ in range(m)] for _ in range(n)]
q = [[0, 0, 0]]
while True:
    nq = []
    for i in q:
        dn = i[2] + d[i[0]] * c[i[1]] 
        if dn < min(h[i[0]][:i[1] + 1]):
            if i[0] < n - 1:
                nq.append([i[0] + 1, i[1] + 1, dn])
            h[i[0]][i[1]] = dn
        if n - i[0] < m - i[1] and i[1] < m - 1:
            nq.append([i[0], i[1] + 1, i[2]])
    if nq == []:
        break
    q = nq
for i in h:
    print(i)
print(min(h[-1]))

Submission status: Accepted

Solution code:
INF = 10 ** 20

n, m = map(int, input().split())
dist = []
weth = []
for _ in range(n):
  dist.append(int(input()))
for _ in range(m):
  weth.append(int(input()))

dp = [INF] * (n + 1)
dp[0] = 0
for i in range(m):
  for j in range(n, 0, -1):
    dp[j] = min(dp[j], dp[j - 1] + dist[j - 1] * weth[i])
print(dp[n])

Submission status: Accepted

Solution code:
INF = 10 ** 20
n, m = map(int, input().split())
dist = [int(input()) for _ in range(n)]
weth = [int(input()) for _ in range(m)]
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(m):
  for j in range(n, 0, -1):
    dp[j] = min(dp[j], dp[j - 1] + dist[j - 1] * weth[i])
print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
d=[input() for _ in xrange(n)]
c=[input() for _ in xrange(m)]
dp=[[float('inf')]*(m+1) for _ in xrange(n+1)]
for i in xrange(m+1):
    dp[0][i]=0
for i in xrange(n):
    for j in xrange(m):
        dp[i+1][j+1]=min(min(dp[i+1]),dp[i][j]+d[i]*c[j])
print(dp[n][m])

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
d=[int(raw_input()) for _ in xrange(n)]
c=[int(raw_input()) for _ in xrange(m)]
dp=[[float('inf')]*(m+1) for _ in xrange(n+1)]
for i in xrange(m+1):
    dp[0][i]=0
for i in xrange(n):
    for j in xrange(m):
        dp[i+1][j+1]=min(min(dp[i+1]),dp[i][j]+d[i]*c[j])
print(dp[n][m])

Submission status: Accepted

Solution code:
N,M = map(int, raw_input().split())
D = [input() for _ in range(N)]
C = [input() for _ in range(M)]
T = [[10**9]*(N+1) for _ in range(M+1)]
T[0][0] = 0
for i in range(M):
    for j in range(N+1):
        if j<N:
            T[i+1][j+1] = min(T[i+1][j+1], T[i][j]+C[i]*D[j])
        T[i+1][j] = min(T[i+1][j], T[i][j])
print T[M][N]

Submission status: Accepted

Solution code:
dp=[[1<<30 for _ in range(1001)] for _ in range(1001)]
dp[0][0]=0
n,m=map(int,input().split())
d=[int(input()) for _ in range(n)]+[0]
c=[int(input()) for _ in range(m)]+[0]
for i in range(m):
    for j in range(n+1):
        if dp[i][j]< dp[i+1][j]:dp[i+1][j]=dp[i][j]
        e=d[j]*c[i]
        if dp[i][j]+e<dp[i+1][j+1]:dp[i+1][j+1]=dp[i][j]+e;
dp=list(zip(*dp[::-1]))
print(min(dp[n]))

Submission status: Accepted

Solution code:
dp=[[1<<30 for _ in range(1001)] for _ in range(1001)]
dp[0][0]=0
n,m=map(int,input().split())
d=[int(input()) for _ in range(n)]+[0]
c=[int(input()) for _ in range(m)]+[0]
for i in range(m):
    for j in range(n+1):
        if dp[i][j]< dp[i+1][j]:dp[i+1][j]=dp[i][j]
        e=d[j]*c[i]
        if dp[i][j]+e<dp[i+1][j+1]:dp[i+1][j+1]=dp[i][j]+e;
print(dp[m][n])

Submission status: Accepted

Solution code:
[n,m] = list(map(int,input().split()))
ds = []
for i in range(n):
  ds.append(int(input()))
cs = []
for i in range(m):
  cs.append(int(input()))
dp = [[0 for i in range(n+1)] for j in range(m+1)]
dp[0][0] = 0
for i in range(m):
  for j in range(n):
    if(i == j):
      dp[i][j] = dp[i-1][j-1] + ds[j] * cs[i]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + ds[j] * cs[i])
print(dp[m-1][n-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dis_lis = []
weth_lis = []

for i in range(n):
    dis_lis.append(int(input()))
for j in range(m):
    weth_lis.append(int(input()))
en_lis = [[100000000000 for i in range(n + 1)] for j in range(m + 1)]
for i in range(m + 1):
    en_lis[i][0] = 0
for i in range(m):
    for k in range(n):
        en_lis[i + 1][k + 1] = min([en_lis[i][k] + weth_lis[i]*dis_lis[k],en_lis[i][k + 1]])
print(en_lis[m][n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
D = [int(input()) for i in range(N)]
C = [int(input()) for i in range(M)]
memo = {}
def dfs(i, j):
    if i == N:
        return 0
    if j == M:
        return 10**9
    if (i, j) in memo:
        return memo[i, j]
    memo[i, j] = res = min(dfs(i+1, j+1) + D[i]*C[j], dfs(i, j+1))
    return res
print(dfs(0, 0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = [int(input()) for _ in range(n)]
c = [int(input()) for _ in range(m)]
h = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
    for j in range(i, m):
        if i == j:
            h[i][j] = h[i -1][j - 1] + d[i] * c[j]
        else:
            h[i][j] = min(h[i][j - 1], h[i - 1][j - 1] + d[i] * c[j])
            
print(h[n - 1][m - 1])

Submission status: Accepted

Solution code:
# AOJ 0611: Silk Road
# Python3 2018.7.4 bal4u

import sys
from sys import stdin
input = stdin.readline

INF = 0x7fffffff
n, m = map(int, input().split())
d = [int(input()) for i in range(n)]
c = [0] + [int(input()) for i in range(m)]
dp = [[INF for j in range(n+1)] for i in range(2)]
dp[0][0] = 0
for i in range(1, m+1):
	for j in range(n+1): dp[i&1][j] = INF
	for j in range(n+1): dp[i&1][j] = dp[1-(i&1)][j]
	for j in range(n):
		if dp[1-(i&1)][j] != INF:
			dp[i&1][j+1] = min(dp[i&1][j+1], dp[1-(i&1)][j]+c[i]*d[j])
print(dp[i&1][n])

Submission status: Accepted

Solution code:
# AOJ 0611: Silk Road
# Python3 2018.7.4 bal4u

import sys
from sys import stdin
input = stdin.readline

INF = 0x7fffffff
n, m = map(int, input().split())
d = [int(input()) for i in range(n)]
c = [int(input()) for i in range(m)]
dp = [[INF for j in range(n+1)] for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
	for j in range(n+1): dp[i+1][j] = dp[i][j]
	for j in range(n):
		if dp[i][j] != INF:
			dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+c[i]*d[j])
print(dp[m][n])

Submission status: Accepted

Solution code:
# AOJ 0611: Silk Road
# Python3 2018.7.4 bal4u

import sys
from sys import stdin
input = stdin.readline

INF = 0x7fffffff
n, m = map(int, input().split())
d = [int(input()) for i in range(n)]
c = [int(input()) for i in range(m)]
dp = [[INF for j in range(n+1)] for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
	dp[i+1] = dp[i][0:n+1]
	for j in range(n):
		if dp[i][j] != INF:
			dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+c[i]*d[j])
print(dp[m][n])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
D = [0]
for _ in range(N):
  D.append(int(input()))

C = [0]
for _ in range(M):
  C.append(int(input()))

INF = float('inf')
dp = [ [INF]*(N+1) for _ in range(M+1) ]
dp[0][0] = 0

# i日目
for i in range(M):
  c = C[i+1]
  # 都市j
  for j in range(min(i+1,N)):
    d = D[j+1]

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+c*d)

res = INF
for i in range(M+1):
  res = min(res, dp[i][-1])

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
C = [ii() for _ in range(N)]
W = [ii() for _ in range(M)]

dp = dp2(float('inf'), N+1, M+1)
dp[0][0] = 0

for i in range(M):
    for j in range(N+1):
        if j+1 <= N:
            dp[i+1][j+1] = min(dp[i][j]+W[i]*C[j], dp[i+1][j+1])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

print(dp[M][N])

Submission status: Accepted

Solution code:
#D問題
N,M = map(int,input().split())
D = [int(input()) for i in range(N)]
C = [int(input()) for j in range(M)]

inf = float("inf")

dp = [[inf for i in range(N+1)] for j in range(M+1)]
dp[0][0] = 0
for j in range(M):
    dp[j+1] = dp[j][0:N+1]
    for i in range(N):
        if dp[j][i] != inf:
            dp[j+1][i+1] = min(dp[j+1][i+1],dp[j][i]+D[i]*C[j])
    #print(dp)
print(dp[M][N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[int(input()) for _ in range(n)]
c=[int(input()) for _ in range(m)]
dp=[[0]*m for _ in range(n)]
for i in range(n):
    for j in range(i,m):
        if i==j:
            dp[i][j]=dp[i-1][j-1]+c[j]*d[i]
        else:    
            dp[i][j]=min(dp[i-1][j-1]+c[j]*d[i],dp[i][j-1])
print(min(dp[n-1][n:m]))

Submission status: Accepted

Solution code:
# AOJ 0611: Silk Road
# Python3 2018.7.4 bal4u
 
import sys
from sys import stdin
input = stdin.readline
 
INF = 0x7fffffff
n, m = map(int, input().split())
d = [int(input()) for i in range(n)]
c = [int(input()) for i in range(m)]
dp = [[INF for j in range(n+1)] for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
    dp[i+1] = dp[i][0:n+1]
    for j in range(n):
        if dp[i][j] != INF:
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+c[i]*d[j])
print(dp[m][n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[[float("inf") for i in range(n+1)] for j in range(m+1)]
dp[0][0]=0
d=[]
for i in range(n):
    d.append(int(input()))
c=[]
for i in range(m):
    c.append(int(input()))
for i in range(1,m+1):
    for j in range(min(i,n)+1):
        dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+d[j-1]*c[i-1])
print(dp[m][n])

Submission status: Runtime Error

Solution code:

def sl(dn,cn):
    global f,tenkou,dist

    if dn>cn or dn<0:
        return False

    if f[dn][cn]==-1:
        a=sl(dn-1,cn-1)+dist[dn]*tenkou[cn]
        b=sl(dn,cn-1)
        c=min(a,b)
        f[dn][cn]=c
        return c
    else:
        return f[dn][cn]

#dn??\?????§???tenkou????????´???
def cost(dn,tenkou):
    global maxd,dist
    val=0
    for i in range(1,dn+1):
        val+=dist[i]*tenkou[i-1]
    return val

dd=input()
maxd,maxc=map(int,dd.split(" "))
dd=[int(input()) for i in range(maxd+maxc)]
dist=dd[:maxd]
dist.insert(0,0)
tenkou=dd[maxd:]
tenkou.insert(0,0)

f=[[-1 for j in range(maxc+1)]for i in range(maxd+1)]

for i in range(1,maxd+1):
    f[i][i]=cost(i,tenkou[1:i+1])

sl(maxd,maxc)

print(f[maxd][maxc])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
D = [int(input()) for i in range(N)]
C = [int(input()) for i in range(M)]
memo = {}
def dfs(i, j):
    if i == N:
        return 0
    if j == M:
        return 10**9
    if (i, j) in memo:
        return memo[i, j]
    memo[i, j] = res = min(dfs(i+1, j+1) + D[i]*C[j], dfs(i, j+1))
    return res
print(dfs(0, 0))

Submission status: Runtime Error

Solution code:
from copy import deepcopy
N, M = map(int, input().split(' '))
D = [int(input()) for i in range(N)]
C = [int(input()) for i in range(M)]
can_stop = N - M

memo = [[] for i in range(N + 1)]
memo[0].append(0)
memo[1].append(D[0] * C[0])

for day in range(1, M):
    tmp = deepcopy(memo)
    for town in range(N):
        for tired in tmp[town]:
            memo[town + 1].append(tired + D[town] * C[day])
print(min(memo[-1]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = [int(input()) for _ in range(n)]
c = [int(input()) for _ in range(m)]
h = [[10e10 for _ in range(m)] for _ in range(n)]
q = [[0, 0, 0]]
while True:
    nq = []
    for i in q:
        dn = i[2] + d[i[0]] * c[i[1]] 
        if dn < min(h[i[0]][:i[1] + 1]):
            if i[0] < n - 1:
                nq.append([i[0] + 1, i[1] + 1, dn])
            h[i[0]][i[1]] = dn
        if n - i[0] < m - i[1] and i[1] < m - 1:
            nq.append([i[0], i[1] + 1, i[2]])
    if nq == []:
        break
    q = nq
print(min(h[-1]))