Problem:


Score : 400 points

Problem Statement

Snuke lives in another world, where slimes are real creatures and kept by some people.
Slimes come in N colors. Those colors are conveniently numbered 1 through N.
Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him a_i seconds.

Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N-1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.

Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints

2≤N≤2,000

a_i are integers.

1≤a_i≤10^9

x is an integer.

1≤x≤10^9

Input

The input is given from Standard Input in the following format:

N x
a_1 a_2 ... a_N

Output

Find the minimum time that Snuke needs to have slimes in all N colors.

Sample Input 1

2 10
1 100

Sample Output 1

12

Snuke can act as follows:

Catch a slime in color 1. This takes 1 second.

Cast the spell. The color of the slime changes: 1 → 2. This takes 10 seconds.

Catch a slime in color 1. This takes 1 second.

Sample Input 2

3 10
100 1 100

Sample Output 2

23

Snuke can act as follows:

Catch a slime in color 2. This takes 1 second.

Cast the spell. The color of the slime changes: 2 → 3. This takes 10 seconds.

Catch a slime in color 2. This takes 1 second.

Cast the soell. The color of each slime changes: 3 → 1, 2 → 3. This takes 10 seconds.

Catch a slime in color 2. This takes 1 second.

Sample Input 3

4 10
1 2 3 4

Sample Output 3

10

Snuke can act as follows:

Catch a slime in color 1. This takes 1 second.

Catch a slime in color 2. This takes 2 seconds.

Catch a slime in color 3. This takes 3 seconds.

Catch a slime in color 4. This takes 4 seconds.



Sample input:
2 10
1 100


Sample output:
12

Submission status: Wrong Answer

Solution code:
import heapq

N, x = map(int, input().split())

INF = 10 ** 15
G = [[] for i in range(N+1)]
check, dist = [0 for j in range(N+1)], [INF for k in range(N+1)]
p, child = [-1 for l in range(N+1)], [-1 for m in range(N+1)]


def dijkstra(s):
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    p[v[0]] = u[1]
                    heapq.heappush(pq, (dist[v[0]], v[0]))

    for i in range(N+1):
        if p[i] != -1:
            child[p[i]] = i


def main():
    a = list(map(int, input().split()))

    for i in range(N):
        G[0].append((i+1, a[i]))
        if i < N - 1:
            G[i+1].append((i+2, x))
    G[N].append((1, x))

    dijkstra(0)

    ans, max_h, sum_a = 0, 0, 0
    for i in range(1, N+1):
        if p[i] == 0:
            v, cnt = i, 0
            sum_a += a[i-1]
            while child[v] != -1:
                cnt += 1
                v = child[v]
            max_h = max(max_h, cnt)
    ans += (max_h+1) * sum_a + max_h * x

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

N, x = map(int, input().split())

INF = 10 ** 15
G = [[] for i in range(N+1)]
check, dist = [0 for j in range(N+1)], [INF for k in range(N+1)]
p, child = [-1 for l in range(N+1)], [-1 for m in range(N+1)]


def dijkstra(s):
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    p[v[0]] = u[1]
                    heapq.heappush(pq, (dist[v[0]], v[0]))

    for i in range(N+1):
        if p[i] != -1:
            child[p[i]] = i


def main():
    a = list(map(int, input().split()))

    for i in range(N):
        G[0].append((i+1, a[i]))
        if i < N - 1:
            G[i+1].append((i+2, x))
    G[N].append((1, x))

    dijkstra(0)

    ans = 0
    for i in range(1, N+1):
        if p[i] == 0:
            v, cnt = i, 0
            while child[v] != -1:
                cnt += 1
                v = child[v]
            ans += (cnt+1) * a[i-1] + cnt * x

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

N, x = map(int, input().split())

INF = 10 ** 15
G = [[] for i in range(N+1)]
check, dist = [0 for j in range(N+1)], [INF for k in range(N+1)]
p, child = [-1 for l in range(N+1)], [-1 for m in range(N+1)]


def dijkstra(s):
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        if u[1] != s:
            child[p[u[1]]] = u[1]

        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    p[v[0]] = u[1]
                    heapq.heappush(pq, (dist[v[0]], v[0]))


def main():
    a = list(map(int, input().split()))

    for i in range(N):
        G[0].append((i+1, a[i]))
        if i < N - 1:
            G[i+1].append((i+2, x))
    G[N].append((1, x))

    dijkstra(0)

    ans = 0
    for i in range(1, N+1):
        if p[i] == 0:
            v, cnt = i, 0
            while child[v] != -1:
                cnt += 1
                v = child[v]
            ans += (cnt+1) * a[i-1] + cnt * x

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, x = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

ans = sum(A)

for i in range(1, n):
    for j in range(n):
        if A[j-i] < A[j]:
            A[j] = A[j-i]
    ans = min(ans, sum(A) + i * x)

print(ans)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))

ans = [[0, 0] for _ in range(n)]
min_ind = a.index(min(a))
ans[min_ind] = [min(a), 0]

for i in range(min_ind + 1, n):
	if a[i] > ans[i-1][0] + x * (ans[i-1][1] + 1):
		ans[i] = [ans[i-1][0], ans[i-1][1] + 1]
	else:
		ans[i] = [a[i], 0]

if a[0] > ans[-1][0] + x * (ans[-1][1] + 1):
	ans[0] = [ans[-1][0], ans[-1][1] + 1]
else:
	ans[0] = [a[0], 0]


for i in range(1, min_ind):
	if a[i] > ans[i-1][0] + x * (ans[i-1][1] + 1):
		ans[i] = [ans[i-1][0], ans[i-1][1] + 1]
	else:
		ans[i] = [a[i], 0]

#print(ans)

print(sum([ans[i][0] for i in range(n)]) + max([ans[i][1] for i in range(n)]) * x)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
from random import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, x = reads()
A = reads()

INF = 1 << 31
smin = [[INF] * N for _ in range(N)]
for i in range(N):
  smin[i][0] = A[i]
  for j in range(1, N):
    smin[i][j] = min(smin[i][j-1], A[(i-j)%N])

ans = INF
for j in range(N):
  h = sum(smin[i][j] for i in range(N)) + x * j
  ans = min(ans, h)
print(ans)

Submission status: Wrong Answer

Solution code:
N,x=map(int,input().split())
nums = list(map(int,input().split()))
costs=[float('inf')]*N
catch = [_ for _ in range(N)]
change = [0]*N

for i in range(N):
  for j in range(N):
    if nums[i-j] + j*x <= costs[i]:
      costs[i] = nums[i-j] + j*x
      catch[i] = (i-j) if 0 <= i-j else (N+i-j)
      change[i] = j
cost = 0
for k in range(N):
  cost += nums[catch[k]]
print(cost + max(change)*x)

Submission status: Wrong Answer

Solution code:
N,x=map(int,input().split())
nums = list(map(int,input().split()))
catch = [_ for _ in range(N)]
change = [0]*N

for i in range(N):
  for j in range(N):
    if nums[i-j] + j*x < nums[i]:
      catch[i] = (i-j) if 0 <= i-j else (N+i-j)
      change[i] = j
cost = 0
for k in range(N):
  cost += nums[catch[k]]
print(cost + max(change)*x)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))

mins = a[:]
result = float("inf")

for k in range(n):
    for i in range(len(mins)):
        mins[i - k] = min(a[i - k], mins[i])
    result = min(x * k + sum(mins), result)

print(result)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())

a = list(map(int, input().split()))
if all(a[0] == v for v in a):
    print(sum(a))
    exit()

def v_1(value):
    v = value + 1
    return v if v < n else 0

visited = [0 for x in range(n)]
result = 0
origin = a[:]
while sum(visited) != n:
    minv = [(i, x1, x2) for i, (x1, x2) in enumerate(zip(a, origin[1:] + [origin[0]])) if x1 < x2 or visited[i]]
    s1 = sum(v[2] for v in minv if not visited[v_1(v[0])])
    s2 = sum(v[1] for v in minv if not visited[v[0]]) + x
    if s1 > s2:
        result += s2
        for v in minv:
            visited[v[0]] = 0
            a[v_1(v[0])] = v[1]
        for v in minv:
            visited[v_1(v[0])] = 1
    else:
        # print("s1", s1, minv, [v for v in minv if not visited[v_1(v[0])]])
        result += s1
        for v in minv:
            visited[v_1(v[0])] = 1
    # print(visited)
    # print("r", result)
# print(" --- ")
print(result)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())

a = list(map(int, input().split()))

def v_1(value):
    v = value + 1
    return v if v < n else 0

visited = [0 for x in range(n)]
result = 0
origin = a[:]
while sum(visited) != n:
    minv = [(i, x1, x2) for i, (x1, x2) in enumerate(zip(a, origin[1:] + [origin[0]])) if x1 < x2 or visited[i]]
    s1 = sum(v[2] for v in minv if not visited[v_1(v[0])])
    s2 = sum(v[1] for v in minv if not visited[v[0]]) + x
    if s1 > s2:
        result += s2
        for v in minv:
            visited[v[0]] = 0
            a[v_1(v[0])] = v[1]
        for v in minv:
            visited[v_1(v[0])] = 1
    else:
        # print("s1", s1, minv, [v for v in minv if not visited[v_1(v[0])]])
        result += s1
        for v in minv:
            visited[v_1(v[0])] = 1
    # print(visited)
    # print("r", result)
# print(" --- ")
print(result)

Submission status: Wrong Answer

Solution code:
n,x = list(map(int,input().split(' ')))
a = list(map(int,input().split(' ')))

tans = 0
for i in range(n):
    ans = a[i]
    for j in range(n):
        e = abs(i-j)
        ans = min(ans, a[j] + e*x, a[j] + (n-e)*x)
    tans += ans

print(tans)

Submission status: Wrong Answer

Solution code:
#AGC004 B

N,x = map(int,input().split())

A = list(map(int,input().split()))

M = min(A)+x

ans = 0
for a in A:
    if a>M: ans += M
    else: ans += a
        
print(ans)

Submission status: Wrong Answer

Solution code:
n, x = map(int,input().split())
slimes = list(map(int,input().split()))
ans = 0

for i in range(n):
    if slimes[i] <= min(slimes) + x:
        ans += slimes[i]
    else:
        ans += min(slimes) + x

print(ans)

Submission status: Wrong Answer

Solution code:
N,x=map(int,input().split())
A=[int(x) for x in input().split()]
dp=[A,A]

#dp[i]:k回魔法を唱えた時にA[i]を手に入れる最小の時間。
#dp=Aで初期化。その後、１〜Nまでのdp[i]はmin(dp[i-1],A[i])で順に更新されていく。
#更新前後のdpを保持するため蟻本P60に記載のある「配列の再利用」を行う。
#各回におけるsum(dp)+k*xを算出して最小値が答え。

#ans初期値は魔法を唱えず、全てを入手した数字（sum(A))
ans=sum(A)
for k in range(1,N):
  cnt=k*x
  ch=True
  for i in range(N):
    dp[(k+1)&1][i]=min(dp[k&1][i-1],A[i])
    cnt+=dp[(k+1)&1][i]
    if cnt>ans:
      ch=False
      break
  if ch:
    ans=min(ans,cnt)
  
print(ans)

Submission status: Wrong Answer

Solution code:
N,x=map(int,input().split())
A=[int(x) for x in input().split()]
dp=[A,A]

#dp[i]:k回魔法を唱えた時にA[i]を手に入れる最小の時間。
#dp=Aで初期化。その後、１〜Nまでのdp[i]はmin(dp[i-1],A[i])で順に更新されていく。
#更新前後のdpを保持するため蟻本P60に記載のある「配列の再利用」を行う。
#各回におけるsum(dp)+k*xを算出して最小値が答え。

#ans初期値は魔法を唱えず、全てを入手した数字（sum(A))
ans=sum(A)
for k in range(1,N):
  cnt=0
  for i in range(N):
    dp[(k+1)&1][i]=min(dp[k&1][i-1],A[i])
    cnt+=dp[(k+1)&1][i]
  ans=min(ans,cnt+k*x)
  
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=0
for i in range(n):
  b+=min(a[i],min([a[j]+int(abs(j-i))*x for j in range(n) if j!=i]))
print(b)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
mem = src[:]
mem2 = src[:]
for i in range(1,N):
    m_cost = X*i
    if m_cost > ans:
        break
    for j in range(N):
        if mem[j] > src[(j-i)%N] + m_cost:
            mem[j] = src[(j-i)%N] + m_cost
            mem2[j] = src[(j-i)%N]
    ans = min(ans, sum(mem2) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
mem = src[:]
mem2 = src[:]
for i in range(1,N):
    m_cost = X*i
    if m_cost > ans:
        break
    for j in range(N):
        if mem[j] > src[(j-i)%N] + X:
            mem[j] = src[(j-i)%N] + m_cost
            mem2[j] = src[(j-i)%N]
    ans = min(ans, sum(mem2) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
mem = src[:]
for i in range(1,N):
    m_cost = X*i
    if m_cost > ans:
        break
    for j in range(N):
        if mem[j] > src[(j-i)%N] + X:
            mem[j] = src[(j-i)%N]
    ans = min(ans, sum(mem) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
mem = src[:]
for i in range(1,N):
    m_cost = X*i
    if m_cost > ans:
        break
    for j in range(N):
        if mem[j] > src[(j-i)%N] + m_cost:
            mem[j] = src[(j-i)%N]
    ans = min(ans, sum(mem) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
dp = src[:]
for i in range(1,N):
    m_cost = X*i
    if m_cost > ans:
        break
    dp2 = dp[:]
    for j in range(N):
        if dp[j] > dp[(j-1)%N] + m_cost:
            dp2[j] = dp[(j-1)%N]
    dp = dp2
    ans = min(ans, sum(dp) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
dp = src[:]
for i in range(1,N):
    m_cost = X*i
    if m_cost > ans:
        break
    dp2 = dp[:]
    for j in range(N):
        if dp[j] > dp[(j-i)%N] + m_cost:
            dp2[j] = dp[(j-i)%N]
    dp = dp2
    ans = min(ans, sum(dp) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
dp = src[:]
for i in range(N):
    m_cost = X*(i+1)
    if m_cost > ans:
        break
    dp2 = dp[:]
    for j in range(N):
        if dp[j] > dp[(j-1)%N] + m_cost:
            dp2[j] = dp[(j-1)%N]
    dp = dp2
    ans = min(ans, sum(dp) + m_cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))

ans = sum(src)
dp = src[:]
for i in range(N):
    if X*(i+1) > ans:
        break
    dp2 = dp[:]
    for j in range(N):
        if dp[j] > dp[(j-1)%N] + X:
            dp2[j] = dp[(j-1)%N]
    dp = dp2
    ans = min(ans, sum(dp) + X*(i+1))
print(ans)

Submission status: Wrong Answer

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))

minlist = {}
m = (N, 1000000001)
for i in range(N):
    if a[i] <= x:
        minlist[i] = (a[i],0)
    if m[1] > a[i]:
        m = (i, a[i])
if len(minlist) == 0:
    minlist[m[0]] = (m[1],0)

i = 0
while len(minlist) < N:
    if i not in minlist:
        if i == 0:
            if N-1 in minlist:
                if minlist[N-1][0] + (minlist[N-1][1]+1)*x < a[i]:
                    minlist[i] = (minlist[N-1][0], minlist[N-1][1]+1)
                else:
                    minlist[i] = (a[i],0)
        else:
            if i-1 in minlist:
                if minlist[i-1][0] + (minlist[i-1][1]+1)*x < a[i]:
                    minlist[i] = (minlist[i-1][0], minlist[i-1][1]+1)
                else:
                    minlist[i] = (a[i],0)
    if i == N-1:
        i = 0
    else:
        i += 1
ans = 0
for i in range(N):
    ans += minlist[i][0]
print(ans + max(minlist.values(),key=lambda x:x[1])[1]*x)

Submission status: Wrong Answer

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))

minlist = {}
m = (N, 1000000001)
for i in range(N):
    if a[i] <= x:
        minlist[i] = (a[i],0)
    if m[1] > a[i]:
        m = (i, a[i])
if len(minlist) == 0:
    minlist[m[0]] = (m[1],0)

i = 0
while len(minlist) < N:
    if i not in minlist:
        if i == 0:
            if N-1 in minlist:
                if minlist[N-1][0] + (minlist[N-1][1]+1)*x <= a[i]:
                    minlist[i] = (minlist[N-1][0], minlist[N-1][1]+1)
                else:
                    minlist[i] = (a[i],0)
        else:
            if i-1 in minlist:
                if minlist[i-1][0] + (minlist[i-1][1]+1)*x <= a[i]:
                    minlist[i] = (minlist[i-1][0], minlist[i-1][1]+1)
                else:
                    minlist[i] = (a[i],0)
    if i == N-1:
        i = 0
    else:
        i += 1
ans = 0
for i in range(N):
    ans += minlist[i][0]
print(ans + max(minlist.values(),key=lambda x:x[1])[1]*x)

Submission status: Wrong Answer

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, x] = [int(input_raw[0]), long(input_raw[1])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(long(input_raw[i]))

    max_shift_num = 0L
    sum_Aj = 0L
    for i in range(N):
        min_time = A[i]
        min_Aj = A[i]
        min_time_shift_num = 0L
        for j in range(N):
            if i == j:
                continue;
            if i - j < 0:
                shift_num = N + (i - j)
            else:
                shift_num = i - j
            time = shift_num * x + A[j]
            if time < min_time:
                min_time = time
                min_Aj = A[j]
                min_time_shift_num = shift_num
        sum_Aj += min_Aj
        if  min_time_shift_num > max_shift_num:
            max_shift_num = min_time_shift_num
    print sum_Aj + max_shift_num * x


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, x] = [int(input_raw[0]), long(input_raw[1])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(long(input_raw[i]))

    max_shift_num = 0
    sum_Aj = 0
    for i in range(N):
        min_time = A[i]
        min_Aj = A[i]
        min_time_shift_num = 0L
        for j in range(N):
            if i == j:
                continue;
            if i - j < 0:
                shift_num = N + (i - j)
            else:
                shift_num = i - j
            time = shift_num * x + A[j]
            if time < min_time:
                min_time = time
                min_Aj = A[j]
                min_time_shift_num = shift_num
        sum_Aj += min_Aj
        if  min_time_shift_num > max_shift_num:
            max_shift_num = min_time_shift_num
    print sum_Aj + max_shift_num * x


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, x] = [int(input_raw[0]), int(input_raw[1])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(long(input_raw[i]))

    max_shift_num = 0
    sum_Aj = 0
    for i in range(N):
        min_time = A[i]
        min_Aj = A[i]
        min_time_shift_num = 0L
        for j in range(N):
            if i == j:
                continue;
            if i - j < 0:
                shift_num = N + (i - j)
            else:
                shift_num = i - j
            time = shift_num * x + A[j]
            if time < min_time:
                min_time = time
                min_Aj = A[j]
                min_time_shift_num = shift_num
        sum_Aj += min_Aj
        if  min_time_shift_num > max_shift_num:
            max_shift_num = min_time_shift_num
    print sum_Aj + max_shift_num * x


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, x] = [int(input_raw[0]), int(input_raw[1])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(int(input_raw[i]))

    max_shift_num = 0
    sum_Aj = 0
    for i in range(N):
        min_time = A[i]
        min_Aj = A[i]
        min_time_shift_num = 0
        for j in range(N):
            if i == j:
                continue;
            if i - j < 0:
                shift_num = N + (i - j)
            else:
                shift_num = i - j
            time = shift_num * x + A[j]
            if time < min_time:
                min_time = time
                min_Aj = A[j]
                min_time_shift_num = shift_num
        sum_Aj += min_Aj
        if  min_time_shift_num > max_shift_num:
            max_shift_num = min_time_shift_num
    print sum_Aj + max_shift_num * x


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
e = 0
d = 0
for i, c in enumerate(a):
    m = a[i]
    k = 0
    for j in range(n):
        l = a[(i - j) % n]
        if l <= m - x:
            m = l
            k = j
    e = max(k, e)
for i, c in enumerate(a):
    m = a[i]
    for j in range(e + 1): m = min(m, a[(i - j) % n])
    d += m
d += e * x
print(d)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
e = 0
d = 0
for i, c in enumerate(a):
    m = a[i]
    k = 0
    for j in range(n):
        l = a[(i - j) % n]
        if l < m - x:
            m = l
            k = j
    e = max(k, e)
for i, c in enumerate(a):
    m = a[i]
    for j in range(e + 1): m = min(m, a[(i - j) % n])
    d += m
d += e * x
print(d)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
d = None
s = 0
for i, k in enumerate(a):
    m = 10 ** 9 + 1
    e = None
    f = None
    for j, l in enumerate(a):
        z = i - j
        if z < 0: z += n
        c = a[j] + z * x
        if c < m:
            m = c
            e = z
            f = a[j]
    s += f
    if d is None or d < e: d = e
s += d * x
print(s)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
d = None
s = 0
for i, k in enumerate(a):
    m = 10 ** 9 + 1
    e = None
    f = None
    for j, l in enumerate(a):
        c = a[j] + abs(i - j) * x
        if c < m:
            m = c
            e = i - j
            if e < 0: e += n
            f = a[j]
    s += f
    if d is None or d < e: d = e
s += d * x
print(s)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))

# 最短時間で色iにするとき、捕まえるときの色と魔法を唱える回数
time = [float('inf')] * n
color = [float('inf')] * n
magic = [0] * n

# 色jで捕まえて、色iになるまで

for i in range(n):
    for j in range(n):
        # 色 n-1 -> 0 の変化をまたぐとき
        if i < j:
            if a[j] + (n - j + i) * x < time[i]:
                time[i] = a[j] + (n - j + i) * x
                color[i] = j
                magic[i] = n - j + i
        else:
            if a[j] + (i - j) * x < time[i]:
                time[i] = a[j] + (i - j) * x
                color[i] = j
                magic[i] = i - j

ans = max(magic) * x
for i in range(n):
    ans += time[i] - magic[i] * x

print(ans)

Submission status: Wrong Answer

Solution code:
n,x = map(int,input().split())
lis = list(map(int,input().split()))
ans = 0
for i in range(n):
    ans += i * x + min(lis)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = 2000 * 1e9
b = [a[j] for j in range(N)]
for i in range(N):
    s = 0
    for j in range(N):
        b[j] = min(b[j], a[j - i])
        s += b[j]
    ans = min(ans, i * x + s)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
cnt = 0
p = a.index(min(a))
while cnt < N:
    ans += min(a[(p + cnt) % N], x + a[p])
    cnt += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
dp = list(map(int,input().split()))
ans = float('inf')
for n in range(N):
    for m in range(N):
       if dp[m] > dp[m-n]:
           dp[m] = dp[m-n]
    ans = min(ans,sum(dp)+n*X)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))
dp = src[:]
ans = float('inf')
for n in range(N):
    t = n*X
    for m in range(N):
       if dp[m] > dp[m-n]:
           dp[m] = dp[m-n]
       t += dp[m]
    ans = min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
src = list(map(int,input().split()))
dp = src[:]
ans = sum(dp)
for n in range(1,N):
    t = n*X
    for m in range(N):
       dp[m] = min(dp[m], dp[m-1])
       t += dp[m]
    ans = min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, x = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans = INF
    m = [INF] * N
    for rotate in range(N):
        total_time = rotate * x
        for i in range(N):
            t = a_list[i - rotate]
            if t < m[i]:
                m[i] = t
            total_time += m[i]
        ans = min(ans, total_time)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, x = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans_list = a_list[:]
    num = [0] * N
    for i in range(N):
        for j in range(N):
            t = a_list[(j - i) % N] + (i * x)
            if t <= ans_list[j]:
                ans_list[j] = t
                num[j] = i

    ans = max(num) * x
    for i in range(N):
        ans += ans_list[i] - (num[i] * x)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, x = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans_list = a_list[:]
    num = [0] * N
    for i in range(N):
        for j in range(N):
            t = a_list[(j - i) % N] + (i * x)
            if t < ans_list[j]:
                ans_list[j] = t
                num[j] = i

    ans = max(num) * x
    for i in range(N):
        ans += ans_list[i] - (num[i] * x)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(): return "".join(list(map(str, ans)))


N, x = rli()
a = rli()

catch_time = 0
magic_time = 0
mi = [2000000000001 for _ in range(N)]
for i in range(N):
    for j in range(N):
        if(mi[i] > a[i-j]+x*j):
            mi[i] = a[i-j]+x*j
            catch_slime = a[i-j]
            magic_time = max(magic_time, x*j)

print(sum(mi) + magic_time)

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(): return "".join(list(map(str, ans)))


N, x = rli()
a = rli()

catch_time = 0
magic_time = 0
for i in range(N):
    mi = 2000000000001
    catch_slime = a[i]
    for j in range(N):
        if(mi > a[i-j]+x*j):
            mi = a[i-j]+x*j
            catch_slime = a[i-j]
            magic_time = max(magic_time, x*j)
    catch_time += catch_slime

print(catch_time + magic_time)

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(): return "".join(list(map(str, ans)))


N, x = rli()
a = rli()

catch_time = 0
magic_time = 0
for i in range(N):
    mi = 2000000000001
    for j in range(N):
        if(mi > a[i-j]+x*j):
            mi = a[i-j]+x*j
            catch_slime = a[i-j]
            magic_time = max(magic_time, x*j)
    catch_time += catch_slime

print(catch_time + magic_time)

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(): return "".join(list(map(str, ans)))


N, x = rli()
a = rli()

dp = [2000000000001 for i in range(N)]
for i in range(N):
    mi = 2000000000001
    for j in range(N):
        mi = min(mi, a[i-j]+x*j)
    if(i == 0):
         dp[i] = mi
    else:
        dp[i] = mi + dp[i-1]
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
s=[[10**12]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if j==0:s[i][j]=a[i]
        else:s[i][j]=min(s[i][j-1],a[(i-j)%n])
ans=10**12
for j in xrange(n):
    tmp=x*j
    for i in xrange(n):
        tmp+=s[i][j]
    ans=min(ans,tmp)
print ans