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: Accepted

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))
memo = A[:]
ans = sum(memo)
for k in range(1, n):
  memo = [min(m, A[itr - k]) for itr, m in enumerate(memo)] 
  ans = min(ans, sum(memo) + x * k)
print(ans)

Submission status: Accepted

Solution code:
n,x = map(int, input().split())
a = list(map(int, input().split()))
cost = a[:]
ans = sum(a)
for k in range(1,n):
  sc = k*x
  for i in range(n):
    if cost[i] > a[i-k]: cost[i] = a[i-k]
    sc += cost[i]
  if sc < ans: ans = sc
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
N, x, *A = map(int, open(0).read().split())
dp = []
for i in range(N):
  dp.append(list(acc((A[(i-j)%N] for j in range(N)),min)))

ans = 10**60
for i,a in enumerate(zip(*dp)):
  ans = min(ans,i*x+sum(a))
print(ans)

Submission status: Accepted

Solution code:
""" 解答AC """

N,x = map(int,input().split())
a = [int(i) for i in input().split()]

# b[i]: 色iを飼うために「捕まえる」の最小値
b = a.copy()

ans = float("inf")
# 魔法を「ちょうど」k回唱える場合
for k in range(N):
    for i in range(N):
        b[i] = min(b[i], a[(i - k) % N])

    ans = min(ans, k * x + sum(b))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, x = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int32)

rec = np.zeros((n, n), dtype=np.int32)
for i in range(n):
    a_tmp = np.roll(np.flipud(a), i)
    np.minimum.accumulate(a_tmp, out=rec[i])

ans = float("inf")
for j in range(n):
    second = rec[:, j].sum() + j * x
    ans = min(ans, second)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, x = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int32)

rec = np.zeros((n, n), dtype=np.int32)
for i in range(n):
    a_tmp = np.concatenate([a[i::-1], a[-1:i:-1]])
    np.minimum.accumulate(a_tmp, out=rec[i])

ans = float("inf")
for j in range(n):
    second = rec[:, j].sum() + j * x
    ans = min(ans, second)

print(ans)

Submission status: Accepted

Solution code:
N,x=map(int,input().split())
a=list(map(int,input().split()))
data=[10**20 for i in range(0,N)]
ans=10**20
test=0
for i in range(0,N):
    flag=0
    for j in range(0,N):
        if a[j-i]<data[j]:
            data[j]=a[j-i]
            flag=1
    if flag==1:
        test=sum(data)+x*i
        if test<ans:
            ans=test

print(ans)

Submission status: Accepted

Solution code:
#b faster
#m_i(k) = min(m_i(k-1), a_(i-k))
# http://agc004.contest.atcoder.jp/data/agc/004/editorial.pdf
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = sum(m)

for k in range(n):
    #cost = x * k
    for i in range(n,2*n):
        m[i-n] = min(m[i-n], a[i-k])
        #cost += mini
    min_cost = min(min_cost, x*k + sum(m))
print(min_cost)

Submission status: Accepted

Solution code:
#b faster
#m_i(k) = min(m_i(k-1), a_(i-k))
# http://agc004.contest.atcoder.jp/data/agc/004/editorial.pdf
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = sum(a)

for k in range(n):
    #cost = x * k
    for i in range(n,2*n):
        m[i-n] = min(m[i-n], a[i-k])
        #cost += mini
    min_cost = min(min_cost, x*k + sum(m))
print(min_cost)

Submission status: Accepted

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

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)

Submission status: Accepted

Solution code:
""" 解答AC """

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

ans = float("inf")

# b[i]: 色iを飼うために「捕まえる」操作時間の最小値
b = a.copy()

# 魔法をちょうどk回唱える場合
for k in range(N):
    for i in range(N):
        b[i] = min(b[i], a[(i-k) % N])

    ans = min(ans, k * x + sum(b))

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 1100100100100100100
    mina = [10000000000 for i in range(n)]
    for i in range(n):
        for j in range(n):
            mina[j] = min(mina[j], a[i - j])
        sumb = sum(mina)
        ans = min(ans, sumb + i * x)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""

入れる場所とそこから波及する場所の最大距離が魔法使用回数

魔法使用回数を決め打ちしてdp？

魔法をp回使うとすると、左p箇所のうち最小の場所から入れるのが最適になる
heapを使うか～

2000 * 2000 * log(2000)
間に合うかなぁ～

4*10**7かぁ

各項からn個左を見た時のaの最小値を求めておく!!!
"""

lis = []

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

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

ans = [x * i for i in range(N)]

for i in range(N):

    nmin = float("inf")
    cnt = 0

    for j in range(i,i-N,-1):

        nmin = min(nmin,a[j])
        ans[cnt] += nmin

        cnt += 1

print (min(ans))

#heapq解(TLE)

"""
import heapq

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

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

ans = float("inf")

maxi = 0

for p in range(N):

    now = x * p

    q = []

    for i in range(-1*p , 0):
        heapq.heappush(q,[a[i] , i])

    for i in range(N):

        heapq.heappush(q , [a[i] , i])

        while q[0][1] < i - p:
            heapq.heappop(q)

        now += q[0][0]
        maxi = max(maxi , i - q[0][1]) 

    ans = min(ans , now)

print (ans)
"""

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))
cost = [ai for ai in a]
res = sum(cost)
for i in range(1, N):
    for j in range(N):
        cost[(j+i)%N] = min(cost[(j+i)%N], a[j])
    res = min(res, sum(cost)+x*i)
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

def main():
  n, x = map(int, input().split())
  A = np.array(input().split()[::-1]*2, dtype=np.int64)
  B = A.copy()[:n]
  ans = float("inf")
  for k in range(n):
    t = x*k + B.sum()
    ans = min(ans, t)
    np.minimum(B, A[k+1:k+n+1], out=B)
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import numpy as np
n, x = map(int, input().split())
A = np.array(input().split()[::-1]*2, dtype=np.int64)
B = A.copy()[:n]
ans = float("inf")
for k in range(n):
  t = x*k + B.sum()
  ans = min(ans, t)
  np.minimum(B, A[k+1:k+n+1], out=B)
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))[::-1]*2
B = A[:n]
ans = float("inf")
for k in range(n):
  t = x*k + sum(B)
  ans = min(ans, t)
  for j in range(n):
    B[j] = min(B[j], A[j+k+1])
print(ans)

Submission status: Accepted

Solution code:
def examA():
    A, B, C = LI()
    ans = min(A*B*(C%2),A*C*(B%2),B*C*(A%2))
    print(ans)
    return

def examB():
    class segment_():
        def __init__(self, A, n, segfunc):
            #####単位元######要設定0or1orinf
            self.ide_ele = inf
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, x = LI()
    A = LI()
    Seg_min = segment_(A, N, lambda a, b: min(a,b))
    ans = inf
    for k in range(N):
        cur = 0
        for j in range(N):
            if j-k>=0:
                now = Seg_min.query(j-k,j+1)
            else:
                now = min(Seg_min.query(0,j+1),Seg_min.query(N-(k-j),N))
#            print(now,k,j)
            cur += now
        ans = min(ans,cur+k*x)

    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Submission status: Accepted

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

B = [[float("inf")] * n for i in range(n)]
for i in range(n):
    for j in range(n):
        B[i][j] = min(B[i-1][j], A[(j-i)%n])

ans = float("inf")
for i in range(n):
    ans = min(ans, sum(B[i])+x*i)        
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
n,x = map(int,input().split())
a = list(map(int,input().split()))
a *= 2
als = deepcopy(a[:n])
ans = [sum(als)]
for k in range(1,n):
  for i in range(n):
    als[i] = min(als[i],a[n+i-k])
  ans.append(sum(als)+x*k)
print(min(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, x = map(int, input().split())
a = list(map(int, input().split()))
res = float("inf")

t = [float("inf")] * N
for k in range(N + 1):
  for i in range(N):
    t[(i + k) % N] = min(t[(i + k) % N], a[i])
  res = min(res, sum(t) + k * x)
print(res)

Submission status: Accepted

Solution code:
n,x = map(int, input().split())
a = list(map(int, input().split()))
cost = a[:]
use = [i for i in range(n)]
ans = sum(a)
for k in range(1,n):
  for i in range(n):
    j = (i-k)%n
    if cost[i] > a[j]:
      cost[i] = a[j]
      use[i] = j
  cur = k*x + sum(cost)
  if ans > cur:
    ans = cur
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・変色の回数を決め打つ
・どの色として捕獲しておくべきだったかが決まる
・左とのminをとることで遷移
"""

import numpy as np

N,X = map(int,readline().split())
A = np.array(read().split(),np.int64)

INF = 10 ** 18
answer = INF
for change in range(N+100):
    x = A.sum() + change * X
    if answer > x:
        answer = x
    x = min(A[0],A[-1])
    A[1:] = np.minimum(A[:-1],A[1:])
    A[0] = x

print(answer)

Submission status: Accepted

Solution code:
# https://misteer.hatenablog.com/entry/AGC004-B

def main():
    N, X = map(int, input().split())
    *A, = map(int, input().split())
    C = A.copy()

    ret = sum(A)
    for magic_count in range(N):
        for slime_idx in range(N):
            C[slime_idx] = min(C[slime_idx], A[slime_idx - magic_count])
            # -magic_countで遡るコストは、Cではなく、A
            # Cだと更に-magic_count程度さかのぼったコストになってしまう
        ret = min(ret, sum(C) + X * magic_count)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    b = [[None for _ in [0]*n] for _ in [0]*n]

    for i in range(n):
        m = a[i]
        for j in range(n):
            k = i-j
            if k < 0:
                k += n
            m = min(m, a[k])
            b[j][i] = m

    m = 10**15
    for i, j in enumerate(b):
        m = min(m, sum(j)+x*i)
    print(m)


main()

Submission status: Accepted

Solution code:
N, x, *A = map(int, open(0).read().split())

ans = float("inf")
for k in range(N):
    ans = min(ans, sum(A) + x * k)
    A = [min(a, b) for a, b in zip(A, A[-1:] + A[:-1])]

print(ans)

Submission status: Accepted

Solution code:
N, x, *A = map(int, open(0).read().split())

ans = float("inf")
for i in range(N):
    ans = min(ans, sum(A) + x * i)
    A = [min(a, b) for a, b in zip(A, [A[-1]] + A[:-1])]

print(ans)

Submission status: Accepted

Solution code:
N,x=map(int,input().split())
a=list(map(int,input().split()))
# スライムの色は0-initialで考える
'''
# スライムiを捕まえてスライムjに変化させるために必要な時間をc[i][j]とする
c=[[-1 for j in range(N)] for i in range(N)]
# スライムjを捕まえてスライムiに変化させるために必要な時間をdとする
d=[[-1 for j in range(N)] for i in range(N)]

for i in range(N):
    for j in range(N):
        d[(i+j)%N][i]=c[i][(i+j)%N]=a[i]+x*j

for ci in c:
    print(ci)
print()
for di in d:
    print(di)
print()
'''
# 
e=[]
for i in range(N):
    e.append([a[(i-k)%N] for k in range(N)])
'''
for ei in e:
    print(ei)
print()
'''
# 
f=[]
for i in range(N):
    fi=[e[i][0]]
    for j in range(1,N):
        fi.append(min(fi[-1],e[i][j]))
    f.append(fi)
'''
for fi in f:
    print(fi)
'''
# k回の魔法で全てのスライムを得るために必要な時間をT[k]とする(0<=k<=N-1)
T=[]
for k in range(N):
    Tk=k*x+sum([f[i][k] for i in range(N)])
    T.append(Tk)

ans=min(T)

print(ans)

# スライムiを最も早く得るために必要なスライムj=s[i]と魔法を唱える回数k[i]=(j-i)%Nを計算する
# →この方針ではWA
'''
s=[d[i].index(min(d[i])) for i in range(N)]
k=[(s[i]-i)%N for i in range(N)]

print(s)
print(k)
'''
# 魔法を唱える回数の最大値(=魔法を唱える回数の合計)*xに，各スライムを捕まえるのに必要な時間Σa[s[i]]を合計する
'''
ans=max(k)*x+sum([a[s[i]] for i in range(N)])
'''
# print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,x=map(int,input().split())
    A=list(map(int,input().split()))
    ans=sum(A)

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

    print(ans)
resolve()

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a.copy()
ans=sum(a)
for k in range(1,n):
  for i in range(n):
    if b[i]>a[i-k]:b[i]=a[i-k]
  d=sum(b)+x*k
  if d<ans:ans=d
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a.copy()
ans=sum(a)
for k in range(n):
  for i in range(n):b[i]=min(b[i],a[i-k])
  ans=min(sum(b)+x*k,ans)
print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
*A, = map(int, input().split())
MAX = 10**18
B = [MAX]*N
ans = MAX
for k in range(N):
    for i in range(N):
        B[i] = min(B[i], A[(i-k) % N])
    ans = min(ans, k*x + sum(B))
print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
INF = float("inf")

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, x = getlist()
	a = getlist()
	B = [[INF] * N for i in range(N)]
	for i in range(N):
		B[0][i] = a[i]
	for i in range(1, N):
		for j in range(N):
			B[i][j] = min(B[i - 1][j], a[(j - i) % N])
	ans = INF
	for i in range(N):
		v = sum(B[i]) + i * x
		ans = min(ans , v)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

ret = float('inf')
dp = [float('inf')] * N
for i in range(N) :
    for j in range(N) :
        dp[(j+i)%N] = min(dp[(j+i)%N], a[j])
    ret = min(ret, sum(dp) + x * i)
print(ret)

Submission status: Accepted

Solution code:
def main():
    N, x = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * N
    ans = float('inf')
    for k in range(N):
        can = k * x
        for i in range(N):
            if k == 0:
                B[i] = A[i]
            else:
                B[i] = min(B[i],A[i-k])
            can += B[i]
        ans = min(ans, can)

    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def it():
    memo = [float('inf')]*N
    for offset,n in zip(range(-N,0),range(N)):
        for i,v in enumerate(memo):
            memo[i] = min(v, A[i+offset])
        yield sum(memo) + n*X

print(min(it()))

Submission status: Accepted

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

# N:  処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
seg_min = [INF]*(2*N0)


def update(index, value):
    index += N0 - 1
    seg_min[index] = value
    while index > 0:
        index = (index - 1) // 2
        seg_min[index] = min(seg_min[index * 2 + 1], seg_min[index * 2 + 2])


def query(first, last):
    first += N0 - 1
    last += N0 - 1
    ret = INF
    while first <= last:
        if not first & 1:
            ret = min(ret, seg_min[first])
        if last & 1:
            ret = min(ret, seg_min[last])
        first = first // 2
        last = last // 2 - 1
    return ret


for i in range(N):
    update(i, A[i])

ans_min = float('inf')
for x_use in range(N//2):
    ans = x * x_use
    for i in range(N//2):
        ans += query(i, i+x_use)
    ans_min = min(ans, ans_min)

print(ans_min)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a_list = list(map(int, input().split()))
time_list = [0] * n
ans = float("inf")
for k in range(n):
    candidate = k * x
    for i in range(n):
        if k == 0:
            time_list[i] = a_list[i]
        else:
            time_list[i] = min(time_list[i], a_list[i-k])
        candidate += time_list[i]
    ans = min(ans, candidate)
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))
d = a[:]
ans = float('inf')
for i in range(n):
    ans = min(ans, sum(d) + x * i)
    for j in range(n):
        d[j] = min(d[j], a[(j - (i + 1) + n) % n])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,x = II()
a = III()

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if j==0:
            dp[i][j] = a[i]
        else:
            dp[i][j] = min(dp[i][j-1], a[(i-j)%N])

ans = float('inf')
for j in range(N):
    now = j*x
    for i in range(N):
        now += dp[i][j]
    if now<ans:
        ans = now

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC4 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,x = LI()
a = LI()
ans = sum(a)
b = a[:]
for k in range(1,n):
    for i in range(n):
        b[i] = min(b[i],a[i-k])
    ans = min(ans,k*x + sum(b))
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

    min_ = np.array(a)

    ans = sum(min_)
    # 魔法を唱える回数 k
    for k in range(1, N):
        min_ = np.minimum(min_, np.roll(min_, 1))
        ans = min(ans, k * x + sum(min_))
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy
input = sys.stdin.readline

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

    min_ = copy.deepcopy(a)

    ans = int(1e15)
    # 魔法を唱える回数 k
    for k in range(N):
        tmp = k * x
        for i in range(N):
            min_[i] = min(min_[i], a[(i-k)%N])
            tmp += min_[i]
        # print(min_)
        ans = min(ans, tmp)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split())
m=[]
for i in range(n):m+=sum(a)+x*i,;*a,=map(min,zip(a,a[-1:]+a))
print(min(m))

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split())
m=1e18
for i in range(n):m=min(m,sum(a)+x*i);*a,=map(min,zip(a,a[-1:]+a))
print(m)

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split())
m=1e18
for i in range(n):m=min(m,sum(a)+x*i);a=[min(t)for t in zip(a,a[-1:]+a)]
print(m)

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split());i,m=0,1e18;exec('m=min(m,sum(a)+x*i);i+=1;a=[min(t)for t in zip(a,a[-1:]+a)];'*n);print(m)

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split())
m=1e18
for i in range(n):
  m=min(m,sum(a)+x*i)
  a=[min(t)for t in zip(a,a[-1:]+a)]
print(m)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = [int(x) for x in input().split()]
T = [0] * N
B = [a for a in A]
for k in range(N):
  for i in range(N):
    B[i] = min(B[i], A[(i - k) % N])
  T[k] = sum(B) + k * x
print(min(T))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=[int(j) for j in input().split()]
ref=[10**18]*n
ans=10**18
for i in range(n):
	ref=[min(ref[j],a[(j+i)%n]) for j in range(n)]
	ans=min(ans,sum(ref)+i*x)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
各スライム（最終状態）に対して、どこで生産すればよかったか。
操作2の回数を決めるごとに計算できる。
"""

N,X = map(int,input().split())
A = np.array(input().split(), dtype=np.int64)

AA = np.concatenate([A,A])

answer = AA[N:].sum()
for n in range(1,N+1):
    np.minimum(AA[1:],AA.copy()[:-1],out=AA[1:])
    answer = min(answer, AA[N:].sum()+X*n)

print(answer)

Submission status: Accepted

Solution code:
prev=lambda n,i,d: i-d if i-d>=0 else n+i-d
N,x=map(int,input().split())
A=list(map(int,input().split()))
dp = A[:]
ans=sum(dp)
for d in range(1,N+1):
    for i in range(N):
        p = prev(N,i,d)
        dp[i]=min(dp[i], A[p])
    ans=min(ans,sum(dp)+d*x)
print(ans)

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split())
b=a[:];r=sum(a)
for i in range(n):
	b=[min(b[j],a[(j+i)%n])for j in range(n)]
	r=min(r,sum(b)+i*x)
print(r)

Submission status: Accepted

Solution code:
n,x,*a = map(int,open(0).read().split())
INF = float("inf")
ref = [INF]*n
ans = INF
for i in range(n):
	ref = [min(ref[j],a[(j+i)%n]) for j in range(n)]
	ans = min(ans,sum(ref)+i*x)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def sol():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))

    B = A.copy()
    ans = sum(B)
    for magic in range(1, N):
        for i in range(N):
            B[i] = min(B[i], A[i - magic])
        ans = min(ans, sum(B) + X * magic)

    print(ans)

sol()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, x = map(int, input().split())
A = list(map(int, input().split()))
m = A.copy()
ans = sum(m)
for k in range(1, N):
    for i in range(N):
        m[i] = min(m[i], A[i-k])
    ans = min(ans, sum(m) + k*x)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A)

# 解説AC
# 何回色変えるかを固定
ans = A.sum()
for k in range(1, N):
    # k 個前までの最小値
    A = np.minimum(A, np.roll(A, 1))
    ans = min(ans, A.sum() + k * X)
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))
b = a[:]
ans = sum(b)
for k in range(1, n):
    b_ = []
    for i in range(n):
        b_.append(min(b[i], a[i - k]))
    b = b_[:]
    ans = min(ans, k * x + sum(b))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, x = map(int, input().split())
    A = list(map(int, input().split()))
    ans = sum(A)
    for i in range(1, N):
        prev = list(A)
        for j in range(N):
            A[j] = min(A[j], prev[(j-1) % N])
        ans = min(ans, sum(A) + i * x)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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):
    slimes = [slimes[i-1] if slimes[i] > slimes[i-1] else slimes[i]
              for i in range(n)]
    cost = min(cost, sum(slimes)+(k+1)*x)
print(cost)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
arr=list(map(int,input().split()))
cost=[10**18]*n
ans=10**18
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: Accepted

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

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

M=[i*x for i in range(N+1)]
M[0]=sum(a)
for i in range(1,N+1):
    b=copy.deepcopy(a)
    for j in range(N):
        b[j]=min(a[j],a[(j-1+N)%N])
    a=copy.deepcopy(b)
    M[i]+=sum(a)
print(min(M))

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,x = map(int,input().split())
a = list(map(int,input().split()))
cost = deepcopy(a)
ret = sum(a)
for i in range(1,n):
    for j in range(n):
        cost[j] = min(cost[j],a[j-i])
    ret = min(ret,sum(cost)+x*i)
print(ret)

Submission status: Accepted

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

ans = sum(a)

b = [a[i] for i in range(n)]
for i in range(1,n):
    c = [b[j] for j in range(n)]
    for k in range(n):
        b[k] = min(c[k],c[k-1])
    ans = min(ans, sum(b)+i*x)
print(ans)