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 sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, x = li()
a = list(li())

a = a + a

# 各色について、どこで捕まえるのが最も良いか考える
mincost = a[:n]
minplace = [i for i in range(n)]
maxbef = 0

for slime in range(n, 2*n):
    for bef in range(n):
        tmp = min(mincost[slime%n], a[(slime-bef)%n] + x*bef)
        if tmp < mincost[slime%n]:
            mincost[slime%n] = tmp
            maxbef = max(maxbef, bef)
            minplace[slime%n] = (slime-bef)%n

ans = x * maxbef

for minpi in minplace:
    ans += a[minpi]

print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
y=a.index(min(a))
a=a[y:]+a[:y]
a[0]=[a[0],0]
for i in range(1,n):
    if a[i]>a[i-1][0]+(a[i-1][1]+1)*x:
        a[i]=[a[i-1][0],a[i-1][1]+1]
    else:
        a[i]=[a[i],0]
y,z=0,0
for i,j in a:
    y+=i
    z=max(z,j)
print(y+x*z)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
A=[int(i) for i in input().split()]
Ans=[]
a1,a2=A[0],0
for i in range(n-1):
  if A[n-i-1]+(i+1)*x<a1:
    a1=A[n-i-1]+(i+1)*x
    a2=i+1
Ans.append([a1,a2])
for i in range(1,n):
  if Ans[-1][0]+x<A[i]:
    Ans.append([Ans[-1][0]+x,Ans[-1][1]+1])
  else:
    Ans.append([A[i],0])
ans,maxx=0,0
for i in range(n):
  ans+=Ans[i][0]-Ans[i][1]*x
  maxx=max(maxx,Ans[i][1])
print(ans+maxx*x)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n, x = map(int, input().split())
slimes = list(map(int, input().split()))

# 魔法を唱える回数を固定
cost = sum(slimes)
for k in range(n):
    tmp = 0
    for i in range(n):
        slimes[i] = min(slimes[i], slimes[(i-k) % n])
        tmp += slimes[i]
    cost = min(cost, tmp+k*x)
print(cost)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
arr=list(map(int,input().split()))
ans=0
shift=0
for i in range(n):
  tmp=10**18
  pos=0
  for j in range(n):
    if arr[(i+j)%n]+x*j<tmp:
      tmp=arr[(i+j)%n]+x*j
      pos=(i+j)%n
      shift=max(shift,j)
  ans+=arr[pos]
print(ans+x*shift)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
arr=list(map(int,input().split()))
cost=[10**10]*n
ans=10**10
for i in range(n):
  for j in range(n):
    cost[j]=min(cost[j],arr[j-i])
  ans=min(ans,x*i+sum(cost))
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
arr=list(map(int,input().split()))
cost=[10**10]*n
ans=10**10
for i in range(n):
  for j in range(n):
    cost[j]=min(cost[j],arr[j-i])
  print(cost)
  ans=min(ans,x*i+sum(cost))
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
arr=list(map(int,input().split()))
ans=0
shift=0
for i in range(n):
  tmp=10**10
  pos=0
  for j in range(n):
    if arr[(i+j)%n]+x*j<tmp:
      tmp=arr[(i+j)%n]+x*j
      pos=(i+j)%n
      shift=max(shift,j)
  ans+=arr[pos]
print(ans+x*shift)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

catch_cnt = [0]*N
tmp_max_dist = 0
for i in range(N):
    dist = 0
    catch_ind = i
    tmp_max_cost = A[i]
    for j in range(1, N):
        prev_ind = (i-j) % N
        dist = j
        cost_catch_prev = A[prev_ind]+x*dist
        if tmp_max_cost > cost_catch_prev:
            tmp_max_cost = cost_catch_prev
            tmp_max_dist = max(tmp_max_dist, dist)
            catch_ind = prev_ind
    catch_cnt[catch_ind] += 1
ans = sum(a*b for a, b in zip(catch_cnt, A))+x*tmp_max_dist
print(ans)

Submission status: Wrong Answer

Solution code:
import copy 
N,x=map(int,input().split())
a=list(map(int,input().split()))
b=copy.deepcopy(a)
M=[i*x for i in range(N+1)]
M[0]+=sum(a)
for i in range(1,N+1):
    for j in range(N):
        a[j]=min(b[j],b[(len(a)+j-1)%len(a)])
    b=a
    M[i]+=sum(a)
print(min(M))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a[a.index(min(a)):]+a[:a.index(min(a))]
j=0
c=b[0]
d=0
for i in range(1,n):
    if c+(i-d)*x<b[i]:j,b[i]=max(j,(i-d)),c
    else:c,d=b[i],i
print(sum(b)+j*x)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

n, x = getList()
nums = getList()
ans = 0
waits = []

def custmin(tgt):
    tc, ts = 1000000000, 0
    for cost, spell in tgt:
        if cost < tc:
            tc, ts = cost, spell
        elif cost == tc and ts > spell:
            tc, ts = cost, spell

    return tc,ts

for i , c in enumerate(nums):
    target = [(tgt + x * ((j+n-i) % n), j) for j, tgt in enumerate(nums)]
    cost, wait = custmin(target)
    ans += nums[wait]

    waits.append((wait+n-i) % n)

print(ans + max(waits) * x)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

n, x = getList()
nums = getList()
ans = 0
waits = []

def custmin(tgt):
    tc, ts = 1000000000, 0
    for cost, spell in tgt:
        if cost < tc:
            tc, ts = cost, spell
        elif cost == tc and ts < spell:
            tc, ts = cost, spell

    return tc,ts

for i , c in enumerate(nums):
    target = [(tgt + x * ((j+n-i) % n), j) for j, tgt in enumerate(nums)]
    cost, wait = custmin(target)
    ans += nums[wait]
    
    waits.append((wait+n-i) % n)

print(ans + max(waits) * x)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

n, x = getList()
nums = getList()
ans = 0
wait = []
for i , c in enumerate(nums):
    _, target =  min([(tgt + x * ((j+n-i) % n), j) for j, tgt in enumerate(nums)])
    ans += nums[target]

    wait.append((target+n-i) % n)

print(ans + max(wait) * x)

Submission status: Wrong Answer

Solution code:
N,x = map(int,input().split())
a = sorted(list(map(int,input().split())))
print(min(N*a[0]+(N-1)*x,sum(a)))

Submission status: Wrong Answer

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

b = [float('inf') for i in range(n)]
m = [0 for i in range(n)]

for i in range(n):
    for j in range(n):
        if b[i]>a[i-j]+j*x:
            b[i] = a[i-j]+j*x
            m[i] = j

print(sum(b)-(sum(m)-max(m))*x)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import copy

def solve(N: int, x: int, a: "List[int]"):
    least = copy.deepcopy(a)
    for _ in range(N):
        for i in range(N):
            if least[i] > least[i-1] + x:
                least[i] = least[i-1] + x
    current = [0] * N
    count = 0
    spent = 0
    while count < N:
        for i, ai in enumerate(a):
            if ai < x and current[i] == 0:
                spent += ai
                count += 1
                current[i] = 1
        if count < N:
            current = [current[j-1] for j in range(N)]
            spent += x
    print(spent)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, x, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import copy

def solve(N: int, x: int, a: "List[int]"):
    least = copy.deepcopy(a)
    for _ in range(N):
        for i in range(N):
            if least[i] > least[i-1] + x:
                least[i] = least[i-1] + x
    current = [0] * N
    count = 0
    spent = 0
    while count < N:
        for i, ai in enumerate(a):
            if ai == least[i] and current[i] == 0:
                spent += ai
                count += 1
                current[i] = 1
        if count < N:
            current = [current[j-1] for j in range(N)]
            spent += x
    print(spent)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, x, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
t=[a[i] for i in range(n)]
sp_cnt=[0 for i in range(n)]
for i in range(1,n):
    if a[n-i]+i*x<t[0]:
        t[0]=a[n-i]
        sp_cnt[0]=i

for i in range(1,n):
    for j in range(n):
        if i-j>=0:
            if a[i-j]+j*x<t[i]:
                t[i]=a[i-j]
                sp_cnt[i]=j
        else:
            if a[n+(i-j)]+j*x<t[i]:
                t[i]=a[n+(i-j)]
                sp_cnt[i]=j

max_sp_cnt=max(sp_cnt)

ans=sum(t)+max_sp_cnt*x
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
t=[a[i] for i in range(n)]
sp_cnt=[0 for i in range(n)]
for i in range(1,n):
    if a[n-i]+i*x<t[0]:
        t[0]=a[n-i]
        sp_cnt[0]=i

for i in range(1,n):
    for j in range(i+1):
        if a[i-j]+j*x<t[i]:
            t[i]=a[i-j]
            sp_cnt[i]=j

max_sp_cnt=max(sp_cnt)

ans=sum(t)+max_sp_cnt*x
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
t=[a[i] for i in range(n)]
sp_cnt=[0 for i in range(n)]
for i in range(1,n):
    if a[n-i]+i*x<t[0]:
        t[0]=a[n-i]
        sp_cnt[0]=i

for i in range(1,n):
    for j in range(i+1):
        if a[i-j]+j*x<t[i]:
            t[i]=a[i-j]
            sp_cnt[i]=j

max_sp_cnt=max(sp_cnt)

ans=sum(t)+max_sp_cnt*x
print(ans,t,sp_cnt)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[a[i] for i in range(n)]
sp_cnt=[0 for i in range(n)]
for i in range(1,n):
    if a[n-i]+i*x<dp[0]:
        dp[0]=a[n-i]+i*x
        sp_cnt[0]=i

for i in range(1,n):
    for j in range(i+1):
        if a[i-j]+j*x<dp[i]:
            dp[i]=a[i-j]+j*x
            sp_cnt[i]=max(sp_cnt[i],j)
            
all_sp_cnt=sum(sp_cnt)
max_sp_cnt=max(sp_cnt)

ans=sum(dp)-(all_sp_cnt-max_sp_cnt)*x
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[a[i] for i in range(n)]
sp_cnt=[0 for i in range(n)]
for i in range(1,n):
    if a[n-i]+i*x<dp[0]:
        dp[0]=a[n-i]+i*x
        sp_cnt[0]=i

for i in range(1,n):
    for j in range(i):
        if a[i-j]+j*x<dp[0]:
            dp[i]=a[i-j]+j*x
            sp_cnt[i]=max(sp_cnt[i],j)
            
all_sp_cnt=sum(sp_cnt)
max_sp_cnt=max(sp_cnt)

ans=sum(dp)-(all_sp_cnt-max_sp_cnt)*x
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[a[i] for i in range(n)]
sp_cnt=[0 for i in range(n)]
for i in range(1,n):
    if a[n-i]+i*x<dp[0]:
        dp[0]=a[n-1]+i*x
        sp_cnt[0]=i

for i in range(1,n):
    for j in range(i):
        if a[i-j]+j*x<dp[0]:
            dp[i]=a[i-j]+j*x
            sp_cnt[i]=max(sp_cnt[i],j)
            
all_sp_cnt=sum(sp_cnt)
max_sp_cnt=max(sp_cnt)

ans=sum(dp)-(all_sp_cnt-max_sp_cnt)*x
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
a=2*a
d=0
e=0
for i in range(n,2*n):
    c=float("inf")
    l=0
    k=0
    for j in range(i+1-n,i+1):
        if c>=a[j]+(i-j)*x:
            c=a[j]+(i-j)*x
            l=a[j]
            k=j
    else:
        e=max(e,i-k)
        d+=l
print(d+e*x)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
a=2*a
d=0
e=0
for i in range(n,2*n):
    c=float("inf")
    k=0
    for j in range(i+1-n,i+1):
        if c>=a[j]+(i-j)*x:
            c=a[j]
            k=j
    else:
        e=max(e,i-k)
        d+=c
print(d+e*x)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from copy import copy


fin = sys.stdin.readline
N, x = [int(elem) for elem in fin().split()]
a_list = [int(elem) for elem in fin().split()]

min_cost_for = copy(a_list)
this_is_from = list(range(N))

max_num_magics = 0
for i, a in enumerate(a_list): 
    for j, other_a in enumerate(a_list):
        if i == j: continue
        num_magics = i - j if j < i else (N - j + i)
        cost = other_a + num_magics * x
        if cost < min_cost_for[i] or \
            (cost == min_cost_for[i] and a_list[this_is_from[i]] > other_a):
            min_cost_for[i] = cost
            max_num_magics = max(num_magics, max_num_magics)
            this_is_from[i] = j


# print(min_cost_for)
# print(max_num_magics)
# print(this_is_from)

total_cost = sum(a_list[origin] for origin in this_is_from) + x * max_num_magics
print(total_cost)

Submission status: Wrong Answer

Solution code:
import sys
from copy import copy


fin = sys.stdin.readline
N, x = [int(elem) for elem in fin().split()]
a_list = [int(elem) for elem in fin().split()]

min_cost_for = copy(a_list)
this_is_from = list(range(N))

max_num_magics = 0
for i, a in enumerate(a_list): 
    for j, other_a in enumerate(a_list):
        if i == j: continue
        num_magics = i - j if j < i else (N - 1 - j + i)
        cost = other_a + num_magics * x
        if cost < min_cost_for[i] or \
            (cost == min_cost_for[i] and a_list[this_is_from[i]] > other_a):
            min_cost_for[i] = cost
            max_num_magics = max(num_magics, max_num_magics)
            this_is_from[i] = j


# print(min_cost_for)
# print(max_num_magics)
# print(this_is_from)

total_cost = sum(a_list[origin] for origin in this_is_from) + x * max_num_magics
print(total_cost)

Submission status: Wrong Answer

Solution code:
import sys
from copy import copy


fin = sys.stdin.readline
N, x = [int(elem) for elem in fin().split()]
a_list = [int(elem) for elem in fin().split()]

min_cost_for = copy(a_list)
this_is_from = list(range(N))

max_num_magics = 0
for i, a in enumerate(a_list): 
    for j, other_a in enumerate(a_list):
        if i == j: continue
        num_magics = i - j if j < i else (N - j + i)
        cost = other_a + num_magics * x
        if cost < min_cost_for[i]:
            min_cost_for[i] = cost
            max_num_magics = max(num_magics, max_num_magics)
            this_is_from[i] = j


total_cost = sum(a_list[origin] for origin in this_is_from) + x * max_num_magics
print(total_cost)

Submission status: Wrong Answer

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

# ans = 10**13
ans = float("inf")

for k in range(N):
    tmp = k * X  

    for i in range(2*N):
        j = (i-k+N*4) % N
        i = i % N
        A[i] = min(A[i], A[j])
    tmp += sum(A)

    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

# ans = 10**13
ans = float("inf")

for k in range(N):
    tmp = k * X  

    for i in range(N):
        j = (i-k+N*2) % N
        A[i] = min(A[i], A[j])
    tmp += sum(A)

    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**13

for k in range(N):
    tmp = k * X  

    for i in range(N):
        j = (i-k+N) % N
        A[i] = min(A[i], A[j])
    tmp += sum(A)

    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**13

for k in range(N+1):
    tmp = k * X  

    for i in range(N):
        j = (i-k+N*2) % N
        A[i] = min(A[i], A[j])
    tmp += sum(A)

    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N,x=map(int,input().split())
A=list(map(int,input().split()))
magic=0
for i in range(N):
    m=0
    v=A[i]
    for j in range(i):
        s=A[j]+(i-j)*x
        if v>s:
            v=s
            m=i-j
        elif v==s:
            m=min(m,i-j)
    for j in range(i+1,N):
        s=A[j]+(i-j+N)*x
        if v>s:
            v=s
            m=i-j+N
        elif v==s:
            m=min(m,i-j+N)
    magic=max(magic,m)
    
AA=A*2
cost=magic*x
for i in range(N,N*2):
    cost+=min(AA[i-magic:i+1])
print(cost)

Submission status: Wrong Answer

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

ans = 10**13

for k in range(N+10):
    tmp = k * X  
    i = 0 
    j = i+k

    for i in range(N):
        j = (i-k+2*N) % N
        A[i] = min(A[i], A[j])
    tmp += sum(A)

    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

ans = 10**13

for k in range(N+10):
    
    tmp = k * X  
    # lst 
    i = 0 
    j = i+k

    for i in range(N):
        j = (i-k+N) % N
        A[i] = min(A[i], A[j])


    for l in A:
        tmp += l
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n, x = map(int, input().split())
    aa = list(map(int, input().split()))
    small = min(aa)
    max_time = small + x
    ans = 0
    for a in aa:
        if a < max_time:
            ans += a
        else:
            ans += max_time
    print(ans)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
alist = list(map(int, input().split()))
mina = min(alist)
mi = alist.index(mina)
suma = mina
for i in range(mi+1, mi+n):
  if alist[i % n] > x + mina:
    suma += x + mina
  else:
    suma += alist[i % n]
print(suma)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
alist = list(sorted(map(int, input().split())))
suma = alist[0]
for a in alist[1:]:
  if a < x:
    suma += a
  else:
    suma += x + alist[0]
print(suma)

Submission status: Wrong Answer

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

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

m=10**10
S=10**10
for i in range(N):
    if m>a[i]:
        m=a[i]
        S=i
L=[10**10 for i in range(N)]

maxM=0
M=0
G=0
L[S]=m
#print(L)
for i in range(N):
    if L[(S+i)%N]+x<a[(S+1+i)%N]:
        M+=x
        G+=m
        if maxM<M:
            maxM=M
    else:
        m=a[(S+1+i)%N]
        G+=m
        M=0
    
    L[(S+1+i)%N]=min(L[(S+i)%N]+x,a[(S+1+i)%N])
#print(L)
print(maxM+G)

Submission status: Wrong Answer

Solution code:
A, B  = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = x
for i in range(1,A):
    for j in range(A):
        dp[i] = min(dp[i],dp[j]+B*min(abs(j-i),abs(A-abs(i-j))))
print(sum(dp))

Submission status: Wrong Answer

Solution code:
A, B  = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = x
for i in range(A):
    for j in range(A):
        dp[i] = min(dp[i],dp[j]+B*min(abs(j-i),abs(A-abs(i-j))))
print(sum(dp))

Submission status: Wrong Answer

Solution code:
A, B  = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = x
for i in range(A):
    for j in range(A):
        dp[i] = min(dp[i],x[j]+B*min(abs(j-i),abs(A-abs(i-j))))
print(sum(dp))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
li=list(map(int,input().split()))
mi=min(li)
ind=-1
for i in range(n):
    if mi==li[i]:
        ind=i
ans=[0]*n
ans[0]=li[ind]
k=0
for i in range(1,n):
    if ind+i>=n:
        k=ind+i-n
    else:
        k=ind+i
    ans[i]=min(li[k],ans[i-1]+x)
print(sum(ans))

Submission status: Wrong Answer

Solution code:
A, B  = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = [inf]*A
for i in range(A):
    for j in range(A):
        dp[i] = min(dp[i],x[j]+B*min(abs(j-i),abs(A-abs(i-j))))
print(sum(dp))

Submission status: Wrong Answer

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

ans = float("inf")
get_dis = lambda bi,i:  (i - bi ) if bi < i else  i+N-bi
for loop in range(0, N+1):
  mxcnt = loop
  NC=[ (i, A[i]) for i in range(N) ]
  for i in range(2*N+1):
    i %= N
    bi = i-1 if i >= 1 else N-1

    #print("get_dis: ", "bi: ", bi, "NCbi0: ", NC[bi][0], "i: ", i,  "dis: ", get_dis(NC[bi][0], i )) 
    if NC[bi][1] < NC[i][1] and get_dis(NC[bi][0],i) <= mxcnt :
        NC[i] = NC[bi]
  tmp = (mxcnt)*X + sum(list(zip(*NC))[1])

  if tmp < ans:
      #print("loop!: ", loop, tmp)
      #print(loop, NC)
      ans = min(tmp, ans)
print(ans)
exit(0)

Submission status: Wrong Answer

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

ans = float("inf")
get_dis = lambda bi,i:  (i - bi ) if bi < i else  i+N-bi
for loop in range(0, N+1):
  mxcnt = loop
  NC=[ (i, A[i]) for i in range(N) ]
  for i in range(2*N+1):
    i %= N
    bi = i-1 if i >= 1 else N-1

    # print("get_dis: ", "bi: ", bi, "NCbi0: ", NC[bi][0], "i: ", i,  "dis: ", get_dis(NC[bi][0], i )) 
    if NC[bi][1] < NC[i][1] and get_dis(NC[bi][0],i) <= mxcnt :
        NC[i] = NC[bi]
  tmp = (mxcnt)*X + sum(list(zip(*NC))[1])

  # if tmp < ans:
  #     print("loop!: ", loop, tmp)
  # print(loop, NC)
  ans = min(tmp, ans)
print(ans)
exit(0)

Submission status: Wrong Answer

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

ans = float("inf")
get_dis = lambda bi,i:  (bi+N - i ) if bi < i else i - bi 
for loop in range(0, N+1):
  mxcnt = loop
  NC=[ (i, A[i]) for i in range(N) ]
  for i in range(2*N+1):
    if i >=N: i%=N    
    bi = i-1
    if bi == -1: bi = N-1

    if NC[bi][1] < NC[i][1] and get_dis(NC[bi][0],i) <= mxcnt :
        NC[i] = NC[bi]
  tmp = (mxcnt)*X + sum(list(zip(*NC))[1])
  ans = min(tmp, ans)
print(ans)
exit(0)

Submission status: Wrong Answer

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

mcost = [ (i, A[i]) for i in range(N)] 

from collections import defaultdict
cnt = defaultdict(int)

for i in range(1,2*N):
    
    bef = (i-1)%N if i >= 1 else N-1
    i %= N
    if mcost[bef][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[bef][0], mcost[bef][1]+X)

mxcnt=0
mxidx=0
for idx,cst in mcost:
    cnt[idx] += 1
    if cnt[idx]>mxcnt:
      mxcnt=cnt[idx] 
      mxidx=idx
if mxcnt == 1:
  print(sum(A)) 
  exit(0)
#print("mxidx: ",mxidx,"mxcnt: ", mxcnt)        


NC=A[:]
for i in range(2*N+1):
  if i >=N: i%=N
  if i != mxidx:
    pcnt=1
    pi=i+1
    v=A[i]
    while pcnt<=mxcnt:
      if pi>=N: pi=pi%N
      if v>=NC[pi]: break
      if pi == mxidx: break
      else:        
        NC[pi]=v
        pcnt+=1
        pi+=1
  if i==mxidx:
    pi=(i+1)%N 
    ccnt=mxcnt-1
    while ccnt:
      NC[pi]=A[i]
      pi=(pi+1)%N
      ccnt-=1

#print("NC:")
#print(NC)
      
ans = (mxcnt-1)*(X) + sum(NC)
print(ans)

Submission status: Wrong Answer

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

mcost = [ (i, A[i]) for i in range(N)] 

from collections import defaultdict
cnt = defaultdict(int)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

if mcost[N-1][1] + X <= mcost[0][1]:
    mcost[0] = ( mcost[N-1][0], mcost[N-1][1]+X)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

mxcnt=0
mxidx=0
for idx,cst in mcost:
    cnt[idx] += 1
    if cnt[idx]>mxcnt:
      mxcnt=cnt[idx] 
      mxidx=idx
if mxcnt==1:
  print(sum(A))
  exit(0)

#print("mxidx: ",mxidx,"mxcnt: ", mxcnt)        
dcnt = defaultdict(lambda:  1 )
NC=A[:]
for i in range(2*N+1):
  if i >=N: i%=N
  if i != mxidx:
    pcnt=1
    pi=i+1
    v=A[i]
    while pcnt<=mxcnt:
      if pi>=N: pi=pi%N
      if v>=NC[pi]: break
      if pi == mxidx: break
      else:        
        NC[pi]=v
        dcnt[i]+=1
        pcnt+=1
        pi+=1
  if i==mxidx:
    pi=(i+1)%N 
    ccnt=mxcnt-1
    while ccnt:
      NC[pi]=A[i]
      pi=(pi+1)%N
      ccnt-=1
     
        
    
#print(dcnt)
#print("NC:")
#print(NC)
      
ans = (mxcnt-1)*(X) + sum(NC)
print(ans)

Submission status: Wrong Answer

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

mcost = [ (i, A[i]) for i in range(N)] 

from collections import defaultdict
cnt = defaultdict(int)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

if mcost[N-1][1] + X <= mcost[0][1]:
    mcost[0] = ( mcost[N-1][0], mcost[N-1][1]+X)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

mxcnt=0
mxidx=0
for idx,cst in mcost:
    cnt[idx] += 1
    if cnt[idx]>mxcnt:
      mxcnt=cnt[idx] 
      mxidx=idx

#print("mxidx: ",mxidx,"mxcnt: ", mxcnt)        
dcnt = defaultdict(lambda:  1 )
NC=A[:]
for i in range(2*N+1):
  if i >=N: i%=N
  if i != mxidx:
    pcnt=1
    pi=i+1
    v=A[i]
    while pcnt<=mxcnt:
      if pi>=N: pi=pi%N
      if v>=NC[pi]: break
      if pi == mxidx: break
      else:        
        NC[pi]=v
        dcnt[i]+=1
        pcnt+=1
        pi+=1
  if i==mxidx:
    pi=(i+1)%N 
    ccnt=mxcnt-1
    while ccnt:
      NC[pi]=A[i]
      pi=(pi+1)%N
      ccnt-=1
     
        
    
#print(dcnt)
#print("NC:")
#print(NC)
      
ans = (mxcnt-1)*(X) + sum(NC)
print(ans)

Submission status: Wrong Answer

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

mcost = [ (i, A[i]) for i in range(N)] 

from collections import defaultdict
cnt = defaultdict(int)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

if mcost[N-1][1] + X <= mcost[0][1]:
    mcost[0] = ( mcost[N-1][0], mcost[N-1][1]+X)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

mxcnt=0
mxidx=0
for idx,cst in mcost:
    cnt[idx] += 1
    if cnt[idx]>mxcnt:
      mxcnt=cnt[idx] 
      mxidx=idx

#print("mxidx: ",mxidx,"mxcnt: ", mxcnt)        
dcnt = defaultdict(lambda:  1 )
NC=A[:]
for i in range(N): 
  if i != mxidx:
    pcnt=1
    pi=i+1
    v=A[i]
    while pcnt<=mxcnt:
      if pi>=N: break
      if v>=NC[pi]: break
      if pi == mxidx: break
      else:        
        NC[pi]=v
        dcnt[i]+=1
        pcnt+=1
        pi+=1
        
    
#print(dcnt)
ans = (mxcnt-1)*(X) + mxcnt*A[mxidx]
for k in dcnt.keys():
        ans += (dcnt[k])*A[k] 

print(ans)

Submission status: Wrong Answer

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

mcost = [ (i, A[i]) for i in range(N)] 

from collections import defaultdict
cnt = defaultdict(int)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

if mcost[N-1][1] + X <= mcost[0][1]:
    mcost[0] = ( mcost[N-1][0], mcost[N-1][1]+X)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)


inf = float("inf")
maxlist = [0] * (N+1)
mxcnt=0

for idx,cst in mcost:
    cnt[idx] += 1
    if cnt[idx]>mxcnt:
      mxcnt=cnt[idx]
    if maxlist[idx] < cst:
        maxlist[idx] = cst

ans = (mxcnt-1)*(X)
for k in cnt.keys():
    if cnt[k] == 1:
        ans += A[k]
    elif cnt[k] > 1:
        ans += (cnt[k])*A[k] 

print(ans)

Submission status: Wrong Answer

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

mcost = [ (i, A[i]) for i in range(N)] 

from collections import defaultdict
cnt = defaultdict(int)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)

if mcost[N-1][1] + X <= mcost[0][1]:
    mcost[0] = ( mcost[N-1][0], mcost[N-1][1]+X)

for i in range(1,N):
    if mcost[i-1][1] + X <= mcost[i][1]:
        mcost[i] = (mcost[i-1][0], mcost[i-1][1]+X)


inf = float("inf")
maxlist = [0] * (N+1)
for idx,cst in mcost:
    cnt[idx] += 1
    if maxlist[idx] < cst:
        maxlist[idx] = cst

ans = 0
for k in cnt.keys():
    if cnt[k] == 1:
        ans += A[k]
    elif cnt[k] > 1:
        ans += (cnt[k]-1)*A[k] + maxlist[k]

print(ans)