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: Time Limit Exceeded

Solution code:
class Segtree(object):
    import math
    def __init__(self, init_val, N, func_type):
        self.func = self.segfunc_min
        self.ide_ele = 10**9 # min
        if func_type == 'max':
            self.func = self.segfunc_max
            self.ide_ele = -10**9 # max
        elif func_type == 'gcd':
            self.func = self.segfunc_gcd
            self.ide_ele = 0 # gcd
        elif func_type == 'lcm':
            self.func = self.segfunc_lcm
            self.ide_ele = 1 # lcm
        elif func_type == 'add':
            self.func = self.segfunc_add
            self.ide_ele = 0 # add

        self.num = 2**(N-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.init_val = init_val

        n = len(self.init_val)
        self.seg[self.num-1:n+self.num-1] = self.init_val[:n]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res

    def segfunc_min(self, a, b):
        if a > b:
            return b
        return a

    def segfunc_max(self, a, b):
        if a >= b:
            return a
        return b

    def segfunc_gcd(self, a, b):
        return math.gcd(a,b)

    def segfunc_lcm(self, a, b):
        return a*b//math.gcd(a,b)

    def segfunc_add(self, a, b):
        return a+b
N,x = map(int,input().split())
a = list(map(int,input().split()))
res = 10**18
seg = Segtree(a+a, 2*N, 'min')
# print(seg.seg)
for k in range(N-1,-1,-1):
    tmp = k*x
    tmp += sum([seg.query(N+i-k,N+i+1) for i in range(N)])
    res = min(res,tmp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class SlideMin:
    """
    スライド最小値\n
    各区間[ai, ai+leng]の最小値を取得する：O(n)\n
    self.que = [(i1, v1), (i2, v2), ..., (ik, vk)]\n
    i1 < ... < ik and v1 < ... < vk
    """
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

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

def sol(n):
    # n個前までの最小値
    B = A + A
    que = SlideMin(n + 1)
    ret = [10**18] * N
    for i, a in enumerate(B):
        que.update(i, a)
        ret[i % N] = min(ret[i % N], que.top()[1])
    return sum(ret) + n * X

ans = sum(A)
for i in range(N):
    ans = min(ans, sol(i))
print(ans)

Submission status: Time Limit Exceeded

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

min_time = A.copy()
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: Time Limit Exceeded

Solution code:
import sys


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_list(cls, lst, INF):
        """
        既存のリストから構築する

        :param lst:
        :param INF:
        :return:
        """
        n = len(lst)
        ins = cls(n, INF)
        ofs = ins.offset
        tree = ins.tree
        tree[ofs:ofs + n] = lst
        for i in range(ofs - 1, 0, -1):
            l = i << 1
            tree[i] = min(tree[l], tree[l + 1])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, x, *aaa = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18
sgt = SegTreeMin.from_list(aaa + aaa, INF)
# k回魔法を使うと決め打つ → その回数で色iを入手するのに最適なのは、i-k～iのスライムの最小値
ans = INF
for k in range(n):
    ans = min(ans, sum(sgt.get_min(i - k, i + 1) for i in range(n, 2 * n)) + k * x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x = na()
a = na()
dp = [i for i in a]
ans = sum(dp)

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

print(ans)

Submission status: Time Limit Exceeded

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


class SegmentTree:
    inf = 2 ** 31 - 1
    
    def __init__(self, n):
        """0-indexed."""
        x = 1
        while x < n:
            x *= 2

        self.n = x
        self.dat = [self.inf] * (2 * x - 1)
        
    def update(self, k, v):
        """Update dat[k] to v."""
        k += self.n - 1
        self.dat[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
            
    def query(self, a, b, k=0, l=0, r=0):
        """Returns min in [a, b)."""
        if l >= r:
            r = self.n
            
        if b <= l or r <= a:
            return self.inf
        
        if a <= l and r <= b:
            return self.dat[k]
        
        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


st = SegmentTree(N)
for i, v in enumerate(A):
    st.update(i, v)

ans = 10 ** 10
for k in range(N):
    b = [0] * N
    for i in range(N):
        if i - k < 0:
            b[i] = min(st.query(0, i + 1), st.query(N - (k - i), N))
        else:
            b[i] = st.query(i - k, i + 1)
    ans = min(ans, k * X + sum(b))
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N,x = map(int,input().split())
    count = N
    N *= 2
    a = list(map(int,input().split()))
    ans = sum(a)
    a += a
    
    def segfunc(x,y):
        return min(x,y)
        
    def init(init_val):
        for i in range(N):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = segfunc(seg[2*i+1],seg[2*i+2])
                
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p > 1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 10**15
    num = 2**(N-1).bit_length()
    seg = [ide_ele]*2*num
    init(a)
    
    for i in range(count-1):
        i += 1
        time = i*x
        for now in range(count):
            ret = query(now+count-i,now+count+1)
            time += ret
        ans = min(ans,time)
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

h=[(0,0)]
while True:
  t,o=heapq.heappop(h)
  if o==2**n-1:
    break
  for j in range(2):
    p=((o<<j)+(o>>(n-j)))%(2**n)
    m,i=min((a[i],i) for i in range(n) if (p>>i)%2==0)
    heapq.heappush(h,(t+m+x*j,p|(2**i)))
print(t)

Submission status: Time Limit Exceeded

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

h=[(0,0)]
while True:
  t,o=heapq.heappop(h)
  if o==2**n-1:
    break
  for j in range(n):
    p=((o<<j)+(o>>(n-j)))%(2**n)
    m,i=min((a[i],i) for i in range(n) if (p>>i)%2==0)
    heapq.heappush(h,(t+m+x*j,p^(2**i)))
print(t)

Submission status: Time Limit Exceeded

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

h=[(0,(0,)*n)]
while True:
  t,o=heapq.heappop(h)
  if all(o):
    break
  m,i=min((a[i],i) for i in range(n) if not o[i])
  heapq.heappush(h,(t+m,o[:i]+(1,)+o[i+1:]))
  heapq.heappush(h,(t+x,tuple(o[(i-1)%n] for i in range(n))))
print(t)

Submission status: Time Limit Exceeded

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

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = 10**18
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += query(i-k, i+1)
            else:
                temp1 = query(0, i+1)
                temp2 = query(n-(k-i), n)
                if temp1 <= temp2:
                    t += temp1
                else:
                    t += temp2
        if t <= ans:
            ans = t
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = float('inf')
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += query(i-k, i+1)
            else:
                temp1 = query(0, i+1)
                temp2 = query(n-(k-i), n)
                if temp1 <= temp2:
                    t += temp1
                else:
                    t += temp2
        if t <= ans:
            ans = t
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = float('inf')
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += query(i-k, i+1)
            else:
                t += min(query(0, i+1), query(n-(k-i), n))
        ans = min(t, ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

rl = sys.stdin.readline


def solve():
    
    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
            a, b = [], []
            
            while L < R:
                if L & 1:
                    a.append(L - 1)
                    L += 1
                if R & 1:
                    R -= 1
                    b.append(R - 1)
                L >>= 1
                R >>= 1
            for i in a + b[::-1]:
                res = self.segfunc(res, self.data[i])
            
            return res
    
    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: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 2 ** (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
        a, b = [], []
        
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        
        return res


def solve():
    N, x = map(int, input().split())
    a = list(map(int, input().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: Time Limit Exceeded

Solution code:
from collections import deque

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

def slide(a, k):
  q = deque()
  ans = 0
  for i in range(-k,0):
    while q and a[q[-1]] > a[i]: q.pop()
    q.append(i)
  for i in range(n):
    if q[0] <= i-k: q.popleft()
    while q and a[q[-1]] > a[i]: q.pop()
    q.append(i)
    ans += a[q[0]]
  return ans

print(min(slide(a,k+1) + x*k for k in range(n)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

rec = [[0] * n for _ in range(n)]
for i in range(n):
    mn = a[i]
    for j in range(n):
        mn = min(mn, a[i-j])
        rec[i][j] = mn

rec = np.array(rec, dtype=np.int32)

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

print(ans)

Submission status: Time Limit Exceeded

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

rec = [[0] * n for _ in range(n)]
for i in range(n):
    mn = a[i]
    for j in range(n):
        mn = min(mn, a[i-j])
        rec[i][j] = mn

sm_li = []
for j in range(n):
    sm = 0
    for i in range(n):
        sm += rec[i][j]
    sm_li.append(sm)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))
 
def segfunc(x, y):
    if x <= y:
      return x
    else:
      return y
 
def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])
 
def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])
 
def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res
 
# identity element
ide_ele = 10**9+1
 
# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num
 
init(A)
 
ans = float('inf')
for k in range(n):
    t = k*x
    for i in range(n):
        if k <= i:
            t += query(i-k, i+1)
        else:
            t += min(query(0, i+1), query(n-(k-i), n))
    ans = min(t, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#b faster
#m_i(k) = min(m_i(k-1), a_(i-k))
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = 10**10

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

Submission status: Time Limit Exceeded

Solution code:
#b
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
a.extend(a)

min_cost = 10**10
for k in range(n):
    cost = x * k
    for i in range(k,k+n):
        mini = min(a[i-k:i+1])
        cost += mini
    min_cost = min(min_cost, cost)
print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
import sys

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        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-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

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

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

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

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**18
    for k in range(n):
        t = 0
        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+k*x, ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def segfunc(x, y):
    return min(x, y)

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        self.num = 2**(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-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

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

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

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

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**18
    for k in range(n):
        t = 0
        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+k*x, ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def segfunc(x, y):
    return min(x, y)

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        self.num = 2**(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-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

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

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

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

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**19
    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)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def segfunc(x, y):
    return min(x, y)

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        self.num = 2**(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-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

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

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**19
    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)

if __name__ == '__main__':
    main()