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()))

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        # set_val
        for i in range(self.n):
            self.seg[i+self.num] = init_val[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, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])

    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res

seg = SegTree(A, 10**18, min)
ans = 10**18
for k in range(n):
    t = k*x
    for i in range(n):
        if k <= i:
            t += seg.query(i-k, i+1)
        else:
            t += min(seg.query(0, i+1), seg.query(n-(k-i), n))
    ans = min(t, ans)
print(ans)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
a = list(map(int,input().split()))
l = [float("INF")]*n
ans = float("INF")
for i in range(n):
    count = x*i
    for j in range(n):
        l[j] = min(l[j],a[(j-i)%n])
        count += l[j]
    ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,x = LI()
    a = LI()

#    N0 = 2**(N.bit_length())
#    st = [INF] * (2*N0)

    def update(i,x):
        i += N0-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = min(st[i*2+1],st[i*2+2])

    def query(l,r):
        l += N0; r += N0
        ret = INF
        while l < r:
            if l % 2:
                ret = min(ret,st[l-1])
                l += 1
            if r % 2:
                r -= 1
                ret = min(ret,st[r-1])
            l >>= 1; r >>= 1
        return ret

#    for i,j in enumerate(a):
#        update(i,j)
    min_a = copy.copy(a)

    ans = INF
    for i in range(N):
        tmp = i * x
        for j in range(N):
            l = j - i
            min_a[j] = min(min_a[j],a[l])
            tmp += min_a[j]
        ans = min(ans,tmp)
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,x = LI()
    a = LI()

    N0 = 2**(N.bit_length())
    st = [INF] * (2*N0)

    def update(i,x):
        i += N0-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = min(st[i*2+1],st[i*2+2])

    def query(l,r):
        l += N0; r += N0
        ret = INF
        while l < r:
            if l % 2:
                ret = min(ret,st[l-1])
                l += 1
            if r % 2:
                r -= 1
                ret = min(ret,st[r-1])
            l >>= 1; r >>= 1
        return ret

    for i,j in enumerate(a):
        update(i,j)

    ans = INF
    for i in range(N):
        tmp = i * x
        for j in range(N):
            l = j - i
            if l < 0:
                l += N
                tmp += min(query(0,j+1),query(l,N))
            else:
                tmp += query(l,j+1)
        ans = min(ans,tmp)
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np

@njit
def main(n,x,a):
    a_ori=a.copy()
    ans=np.sum(a)
    for i in range(1,n):
        tmp=x*i
        for j in range(n):
            a[j]=min(a[j],a_ori[j-i])
            tmp+=a[j]
        ans=min(ans,tmp)
    print(ans)

if __name__=='__main__':
    n,x=map(int,input().split())
    a=np.array(list(map(int,input().split())),np.int32)
    main(n,x,a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,x = map(int,input().split())
A = list(map(int,input().split()))

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self, i=None):
        if i is None:
            return self.data[self.l:self.l + self.N]
        else:
            return self.data[self.l+i]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i, j = i//2, j//2
        return s


A2 = A+A
inf = 10**15
cand = []
seg = SegmentTree(A2,min,inf)
for i in range(N):
    temp = i*x
    for j in range(N):
        temp += seg.get(N+j-i,N+j+1)
    cand.append(temp)
print(min(cand))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, x = map(int, readline().split())
    a = list(map(int, readline().split()))
    ans = sum(a)
    prev = a[:]

    for cnt in range(1, n):
        score = cnt * x
        cur = [0] * n
        for i in range(n):
            cur[i] = min(prev[i], prev[(i - 1) % n])
        score += sum(cur)
        ans = min(ans, score)
        prev = cur

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,x = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    pm = a*1
    mi = sum(a)
    for i in range(1,n):
        mii = x*i
        pp = pm*1
        for j in range(n):
            pm[n-1-j] = min(pp[n-1-j],a[n-1-j-i])
            mii += pm[n-1-j]
        if mi > mii:
            mi = mii
    print(mi)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# colorful slimes
class SegTree():
    # 1-indexed
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, X = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(3*N)]
for i in range(N):
    B[i] = B[i+N] = B[i+2*N] = A[i]

T = SegTree(B, min, 10**10)
ans = 10**30
# ちょうどN回の要素増加が必要。
# セグメント木を利用した解答
for cnt in range(N+1):
    # cnt回数だけループ操作を行うとする。
    # N回以上のループを伴う解答は自明回より不最適なのでのぞいて良い。
    sub = X*cnt
    for i in range(1+N, 2*N+1):
        sub += T.query(i-cnt, i+1)
    ans = min(sub, ans)
print(ans)

Submission status: Accepted

Solution code:
# colorful slimes
class SegTree():
    # 1-indexed
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, X = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(3*N)]
for i in range(N):
    B[i] = B[i+N] = B[i+2*N] = A[i]

T = SegTree(B, min, 10**10)
ans = 10**30
# ちょうどN回の要素増加が必要。
# セグメント木を利用した解答
for cnt in range(N+1):
    # cnt回数だけループ操作を行うとする。
    # N回以上のループを伴う解答は自明回より不最適なのでのぞいて良い。
    sub = X*cnt
    for i in range(1+N, 2*N+1):
        sub += T.query(i, i+1+cnt)
    ans = min(sub, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

INF = 10**18
dp = np.full((N, N + N), INF, np.int64)
dp[0] = np.concatenate((A, A))
for n in range(1, N):
    dp[n, 1:] = np.minimum(dp[n - 1, 1:], dp[n - 1, :-1])
dp = dp[:, N:]

x = dp.sum(axis=1) + X * np.arange(N)
print(x.min())

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = tuple(map(int, input().split()))

inf = 10 ** 13
res = inf
b = [inf] * n

for x in range(n):
    bsum = 0
    for i in range(n):
        j = (i - x) % n
        b[i] = min(b[i], a[j])
        bsum += b[i]
    res = min(res, k * x + bsum)

print(res)

Submission status: Accepted

Solution code:
INF = 2**31-1
class segtree():
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.data = [INF]*((2*self.N0)+1)

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # 区間[l, r)の最小値
    def get(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
N, x = map(int,input().split())

s_tree = segtree(2*N) #N⇒1になるので二倍の配列を準備
arr = list(map(int,input().split()))

for i in range(N):
    s_tree.update(i, arr[i])
    s_tree.update(i+N, arr[i])

ans = float("inf")
for i in range(N):#i = 魔法をかける回数
    tmp = i * x
    for k in range(N,2*N):#i回魔法をかけてスライムkに変更できうる区間の中で、最小コストのスライムを選ぶ 
        tmp += s_tree.get(k-i,k+1)
    ans = min(ans,tmp) #合計コストが答のものが答
    
print(ans)

Submission status: Accepted

Solution code:
# B - Colorful Slimes
N,x = map(int,input().split())
A = list(map(int,input().split()))
B = A[:]
ans = sum(A)
for k in range(1,N):
    for i in range(N):
        B[i] = min(B[i],A[(i-k)%N])
    ans = min(ans,sum(B)+k*x)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



from queue import deque
n,x = map(int, input().split())
A = list(map(int, input().split()))

def sub(p):
    k = p
    res = []
    q = deque([])
    a = A + A[:k-1]
    # q: i0<i1<,..., a_i0>a_i1>,...であるようなi0, i1,... のキュー
    for i,num in enumerate(a):
        while q and a[q[-1]]>num:
            q.pop()
        q.append(i)
        if q[0]<=i-k:
            q.popleft()
        if i>=k-1:
            m = a[q[0]] # i-k+1,...iの中の最小値
            res.append(m)
    return sum(res)


ans = 10**15
for p in range(n):
    ans = min(ans, sub(p+1) + x*p)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



from queue import deque
n,x = map(int, input().split())
a = list(map(int, input().split()))

def sub(p):
    k = p
    res = []
    q = deque([])
    # q: i0<i1<,..., a_i0>a_i1>,...であるようなi0, i1,... のキュー
    for i,num in enumerate(a):
        while q and a[q[-1]]>num:
            q.pop()
        q.append(i)
        if q[0]<=i-k:
            q.popleft()
        if i>=k-1:
            m = a[q[0]] # i-k+1,...iの中の最小値
            res.append(m)
    for j,num in enumerate(a):
        if len(res)>=n:
            break
        while q and a[q[-1] if q[-1]<n else q[-1]-n]>num:
            q.pop()
        q.append(j+n)
        if q[0]<=j+n-k:
            q.popleft()
        m = a[q[0] if q[0]<n else q[0]-n] # i-k+1,...iの中の最小値
        res.append(m)
    return sum(res)


ans = 10**15
for p in range(n):
    ans = min(ans, sub(p+1) + x*p)
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
A=list(map(int,input().split()))
ans=float("INF")
dp=[[A[i]]*n for i in range(n)]
for l in range(n):
  a=A[l:]+A[:l]
  a=a[::-1]
  for i in range(n-1):
    dp[l][i+1]=min(dp[l][i],a[i])
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=dp[j][i]
  ans=min(tmp+x*i,ans)
print(ans)

Submission status: Accepted

Solution code:
N,x = map(int,input().split())
a = list(map(int,input().split()))
res = 10**18
d = [[0]*N for _ in range(N)]
for i in range(N):
    d[i][0] = a[i]
    for k in range(1,N):
        d[i][k] = min(d[i][k-1], a[i-k])

for k in range(N-1,-1,-1):
    tmp = k*x
    tmp += sum([d[i][k] for i in range(N)])
    res = min(res,tmp)
print(res)

Submission status: Accepted

Solution code:
INF = 2**31-1
class SegmentTree():
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.data = [INF]*((2*self.N0)+1)

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # 区間[l, r)の最小値
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 10**18
segtree = SegmentTree(2*n)
for i in range(n):
    segtree.update(i, a[i])
    segtree.update(i+n, a[i])


for k in range(n):
    temp = k*x
    for i in range(n, 2*n):
        temp += segtree.query(i-k, i+1)
    ans = min(ans, temp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(A[Q[0]])
    return res[K - 1:]

# 0〜N-1回、魔法を唱える方法で場合分け、スライド最小値
N, X = lr()
A = lr()
INF = 10 ** 15
A += A
answer = INF
for t in range(N):
    temp = t * X
    mi = slide_min(A, t + 1)
    mi = mi[N-t:]
    temp += sum(mi)
    if temp < answer:
        answer = temp

print(answer)

Submission status: Accepted

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

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]
  ans = min(ans, sum(b) + k*x)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from functools import reduce
N,x,*A = map(int, open(0).read().split())
dp =[list(accumulate((A[i-j] for j in range(N)),min)) for i in range(N)]
ans = reduce(min, (i*x+sum(a) for i,a in enumerate(zip(*dp))))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from functools import reduce
N,x,*A = map(int, open(0).read().split())
dp = [0]*N
for i in range(N):
  dp[i] = list(accumulate((A[i-j] for j in range(N)),min))
ans = reduce(min, (i*x+sum(a) for i,a in enumerate(zip(*dp))))
print(ans)

Submission status: Accepted

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

ans = sum(A)
for x in range(1, N + 1):
    for i in range(N)[::-1]:
        if B[i] > A[i - x]:
            B[i] = A[i - x]
    ans = min(ans, sum(B) + x * X)
print(ans)

Submission status: Accepted

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

min_time = [a for a in A]
ans = 10**15
for t in range(N):
  time = t*x
  for i in range(N):
    j = (i - t) % N
    min_time[i] = min(min_time[i], A[j])
    time += min_time[i]
  ans = min(ans, time)

print(ans)

Submission status: Accepted

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

N, x = map(int, input().split())
a = list(map(int, input().split()))
INF = 10**18
cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][0] = a[i]
    for j in range(1, N):
        k = (i - j) % N
        cost[i][j] = min(a[k], cost[i][j - 1])
total = [sum(cost[i][j] for i in range(N)) for j in range(N)]
print(min(total[i] + x * i for i in range(N)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        return res


def solve():
    N, x = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    seg_tree = SegmentTree(a, min, 10 ** 15)
    ans = 10 ** 15
    for i in range(N):
        get_cost = 0
        for j in range(N):
            if i <= j:
                get_cost += seg_tree.query(j - i, j + 1)
            else:
                get_cost += min(seg_tree.query(0, j + 1), seg_tree.query(N - i + j, N))
        ans = min(ans, i * x + get_cost)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
A = list(map(int,input().split()))
inf = float('inf')
ans = inf
dp = [[inf]*n for i in range(n)]
for i in range(n):
    cnt = x*i
    for j in range(n):
        if i == 0:
            dp[i][j] = A[j]
        cnt += dp[i][j]
        if i != n-1:
            dp[i+1][(j+1)%n] = min(dp[i+1][(j+1)%n],dp[i][j])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

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

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
input = sys.stdin.buffer.readline
import copy

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = copy.deepcopy(a)
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = a.copy()
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

# array size nxn filled with zeroes
minrange = [[0 for j in range(n)] for i in range(n)]
for r in range(n):
    for l in range(r):
        minrange[l][r] = min(minrange[l][r-1], a[r])
    minrange[r][r] = a[r]

res = int(1e18) # 10^18 is basically infinity
for k in range(n):
    cur = k*x
    for i in range(n):
        if i-k >= 0:
            cur += minrange[i-k][i]
        else:
            cur += min(minrange[0][i], minrange[i-k+n][n-1])
    res = min(res, cur)

print(res)

Submission status: Accepted

Solution code:
import copy

n,x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
now = a.copy()
for i in range(1,n):
  for j in range(n):
    now[j] = min(now[j],a[(j+i)%n])
  ans = min(ans,sum(now) + x * i)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class Segtree:
    def __init__(self, A, ide_ele, segfunc, initialize=True):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        if initialize:
            self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
            for i in range(self.size - 1, 0, -1):
                self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])
        else:
            self.data = [ide_ele] * (2 * self.size)

    def update(self, k, x):
        k += self.size
        self.data[k] = x
        while k:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

n, x = LI()
A = LI()
ans = INF
seg = Segtree(A, INF, min)
for i in range(n):
    ret = i * x
    for j in range(n):
        if j - i >= 0:
            ret += seg.query(j - i, j + 1)
        else:
            ret += min(seg.query(0, j + 1), seg.query(n - (i - j), n))
    ans = min(ans, ret)


print(ans)

Submission status: Accepted

Solution code:
import sys

rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k >>= 1
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        return res


def solve():
    N, x = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    seg_tree = SegmentTree(a, min, 10 ** 15)
    ans = 10 ** 15
    for i in range(N):
        get_cost = 0
        for j in range(N):
            if i <= j:
                get_cost += seg_tree.query(j - i, j + 1)
            else:
                get_cost += min(seg_tree.query(0, j + 1), seg_tree.query(N - i + j, N))
        ans = min(ans, i * x + get_cost)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        return res


def solve():
    N, x = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    seg_tree = SegmentTree(a, min, 10 ** 15)
    ans = 10 ** 15
    for i in range(N):
        get_cost = 0
        for j in range(N):
            if i <= j:
                get_cost += seg_tree.query(j - i, j + 1)
            else:
                get_cost += min(seg_tree.query(0, j + 1), seg_tree.query(N - i + j, N))
        ans = min(ans, i * x + get_cost)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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