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:
n, x = map(int, input().split())
A = list(map(int, input().split()))

def segfunc(x, y):
    return min(x, 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**19
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:
n, x = map(int, input().split())
A = list(map(int, input().split()))

def segfunc(x, y):
    return min(x, 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:
"""

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

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

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

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

4*10**7かぁ
"""

import heapq

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

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

ans = float("inf")

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]

    ans = min(ans , now)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = MAP()
A = LIST()

dp = list2d(N, N, INF)
for i in range(N):
    k = 0
    for j in range(i, i-N, -1):
        j %= N
        dp[i][k] = min(dp[i][(k-1)%N], A[j])
        k += 1

ans = [0] * N
for i in range(N):
    for j in range(N):
        ans[j] += dp[i][j]
    ans[i] += i * X
print(min(ans))

Submission status: Time Limit Exceeded

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

class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res
e = dd(list)
for k in range(N + 1):
  for i in range(N):
    e[N].append(((i + k) % N, a[i]))
    e[(i + k) % N].append((N, a[i]))
  pri = prim(N, e)
  res = min(res, pri.MSTcost() + k * x)
print(res)

Submission status: Time Limit Exceeded

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):
  d=0
  for i in range(n):
    b[i]=min(b[i],a[i-k])
    d+=b[i]
  ans=min(d+x*k,ans)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

inf = float('inf')
ans = inf

time = [[inf] * N for _ in range(N)]

for i in range(N):
    tmp = inf
    for k in range(N):
        ni = i + k
        if ni > N - 1:
            ni %= N
        tmp = min(tmp, a[ni])
        time[i][k] = tmp

# k回魔法を唱える
for k in range(N):
    res = k*x
    for i in range(N):
        res += time[i][k]
    ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

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

inf = float('inf')
ans = inf

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [inf for _ in range(2*self.N)]
    
    def update(self, k, x):
        k += self.N-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.N
        R = r + self.N
        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

st = SegmentTree(N)
for i, ai in enumerate(a):
    st.update(i, ai)

def time(i, k):
    if i+k+1 <= N:
        tmp = st.query(i, i+k+1)
    else:
        tmp = min(st.query(0, (i+k) % N + 1), st.query(i, N))
    return tmp

# k回魔法を唱える
for k in range(N):
    res = k*x
    for i in range(N):
        res += time(i, k)
    ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))
d = a.copy()
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: Time Limit Exceeded

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

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

dp = [[None for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[0][i] = A[i]

ans = sum(dp[0])
for d in range(1, N):
    for i in range(N):
        dp[d][i] = min(dp[d-1][i], A[(i+d)%N])
    ans = min(ans, sum(dp[d])+X*d)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
u = list(map(int, input().split()))
a, b = u[0], u[1]
c = list(map(int, input().split()))
d = [10**9 for i in range(a)]
ans = 10 ** 19
for i in range(a):
    nans = i * b
    for j in range(a):
        d[j] = min(d[j], c[(j - i + a) % a])
        nans += d[j]
    ans = min(ans, nans)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
N,x=map(int,input().split())
a=list(map(int,input().split()))
c=[[None]*N for i in range(N)]
for j in range(N):
    for i in range(N):
        if j==0:
            c[j][i]=a[i]
        else:
            c[j][i]=min(c[j-1][i-1],a[i])
ans=2*10**12
for i in range(N):
    ans=min(ans,sum(c[i])+x*i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,x = map(int,input().split())
*A, = map(int,input().split())
c = [A[:] for _ in [0]*(N)]
ans = sum(A)
for i in range(1,N):
    for j in range(N):
        c[i][j] = min(c[i-1][j-1],c[i][j])
    ans = min(ans,sum(c[i])+x*i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
	N, x = input().split(" ")
	N = int(N)
	x = int(x)
	a = []
	for e in input().split(" "):
		a.append(int(e))

	min_cost = []
	for i in range(N):
		min_cost.append([0] * N)

	min_total_cost = -1
	for k in range(N):
		temp_sum = 0
		if k==0:
			for i in range(N):
				min_cost[k][i] = a[i]
				temp_sum += min_cost[k][i]
		else:
			for i in range(N):
				idx = (i-k) % N
				min_cost[k][i] = min(min_cost[k-1][i], a[idx])
				temp_sum += min_cost[k][i]

		if min_total_cost == -1:
			min_total_cost = (k * x) + temp_sum
		else:
			temp = (k * x) + temp_sum
			if temp < min_total_cost:
				min_total_cost = temp

	print (min_total_cost)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
	N, x = input().split(" ")
	N = int(N)
	x = int(x)
	a = []
	for e in input().split(" "):
		a.append(int(e))

	min_cost = []
	for i in range(N):
		min_cost.append([0] * N)

	min_total_cost = -1
	for k in range(N):
		if k==0:
			for i in range(N):
				min_cost[k][i] = a[i]
		else:
			for i in range(N):
				idx = (i-k) % N
				min_cost[k][i] = min(min_cost[k-1][i], a[idx])

		if min_total_cost == -1:
			min_total_cost = (k * x) + sum(min_cost[k])
		else:
			temp = (k * x) + sum(min_cost[k])
			if temp < min_total_cost:
				min_total_cost = temp

	print (min_total_cost)

Submission status: Time Limit Exceeded

Solution code:
n,x=map(int,input().split())
A=[int(i) for i in input().split()]
B=[float("inf")]*n
ans=float("inf")
for i in range(n):
  ans_i=i*x
  for j in range(n):
    B[j]=min(B[j],A[j-i])
    ans_i+=B[j]
  ans=min(ans,ans_i)
print(ans)

Submission status: Time Limit Exceeded

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

no_magic_cost = sum(slimes)


b_prev = [float('inf')]*n
for i in range(n):
    b_prev[i] = slimes[i]

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

Submission status: Time Limit Exceeded

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

no_magic_cost = sum(slimes)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

# a_i, a_{i + 1}, ..., a_j の最小値
@lru_cache(maxsize=None)
def f(i, j):
    return (
        a[i] if i == j else
        min(f(i, (j - 1) % N), a[j])
    )

# 変色回数を0からN-1まで決め打ちして解を求める
ans = min(
    sum(f(i, (i + k) % N) for i in range(N)) + k * x
    for k in range(N)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x=map(int, input().split())
lst=list(map(int, input().split()))
ms=lst
lst=lst*2
ans=10**15
s=0
for i in range(n):
    s=i*x
    for j in range(n):
        ms[j]=min(ms[j],lst[n+j-i])
        s+=ms[j]
    ans=min(ans,s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x=map(int, input().split())
lst=list(map(int, input().split()))
lst=lst*2
ans=10**15
s=0
for i in range(n):
    s=i*x
    for j in range(n):
        s+=min(lst[n+j-i:n+j+1])
    ans=min(ans,s)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))
min_a = {}
for i in range(N):
    min_a[i] = a[i]
ans = 10 ** 18
for i in range(N):
    s = x * i
    for j in range(N):
        min_a[j] = min(min_a[j], a[(i + j) % N])
        s += min_a[j]
    ans = min(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, x = map(int, input().split())
a = np.array(list(map(int, input().split())))
min_a = a.copy()
ans = 10 ** 18
for i in range(N):
    s = x * i
    for j in range(N):
        min_a[j] = min(min_a[j], a[(i + j) % N])
        s += min_a[j]
    ans = min(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))
min_a = []
for i in a:
    min_a.append(i)
ans = 10 ** 18
for i in range(N):
    s = x * i
    for j in range(N):
        min_a[j] = min(min_a[j], a[(i + j) % N])
        s += min_a[j]
    ans = min(ans, s)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = float("inf")
for loop in range(0, N+1):
  mxcnt = loop
  NC=A[:]
  for i in range(2*N+1):
    if i >=N: i%=N    
    pcnt=1
    pi=(i+1)%N
    v=A[i]
    while pcnt<=mxcnt:
      if v>=NC[pi]: break   
      NC[pi]=v
      pcnt+=1
      pi=(pi+1)%N
    tmp = (mxcnt)*X + sum(NC)
    ans = min(tmp, ans)
    # print("loop: ", loop, NC)
print(ans)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x = map(int, input().split())
DP = np.zeros((n,n), dtype=np.int32)
a = np.array(list(map(int, input().split())), dtype=np.int32)
DP[0] = a
for i in range(n-1):
    for j in range(n):
        DP[i+1][j] = min(DP[i][j], DP[i][j-1])
ans = float("inf")
for i in range(n):
    ans = min(ans, sum(DP[i])+i*x)
print(int(ans))

Submission status: Time Limit Exceeded

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

# DP[i][j] = i回以下魔法を掛けられてj色のスライムができるとき、最初のコストの最小値
DP = [[0]*n for i in range(n)]
DP[0] = a
for i in range(n-1):
    for j in range(n):
        DP[i+1][j] = min(DP[i][j], DP[i][j-1])
ans = float("inf")
for i in range(n):
    ans = min(ans, sum(DP[i])+i*x)
print(ans)

Submission status: Time Limit Exceeded

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

#p[i色のスライム][j回まで色を変えられる]=色変えのコストを含まない最小コスト
p = [[0]*n for i in range(n)]
cnt = [[0]*n for i in range(n)]
#print(p)
for i in range(n):
  p[i][0]=a[i]
  for j in range(1,n):
    if i-j>=0:
      p[i][j]=min(a[i-j],p[i][j-1])
    elif i-j == -1:
      p[i][j]=min(a[n-1],p[i][j-1])
    else:  
      p[i][j]=min(a[n-(j-i)],p[i][j-1])
p = list(zip(*p))
ans = sum(p[0])
for i in range(1,n):
  ans = min(ans,sum(p[i])+x*i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))
INF = float("inf")
num = INF
rec = [INF] * N
for k in range(N):
    tmp = 0
    for j in range(N):
        rec[j] = min(rec[j], a[j - k])
        tmp += rec[j]

    num = min(tmp + k * x, num)

print(num)

Submission status: Time Limit Exceeded

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

INF = float('inf')
dp = [[INF] * (n+10) for _ in range(n)]

for i in range(n):
    for k in range(n):
        if k == 0:
            dp[i][k] = a[i]
        else:
            dp[i][k] = min(dp[i][k-1], a[(i-k)%n])

ans = INF

for k in range(n):
    tmp = x * k
    for i in range(n):
        tmp += dp[i][k]
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

ans = sum(A)
A = A+A

for k in range(1,N):
    L = [0]*N
    for l in range(N):
        T = A[N+l-k:N+l+1]
        L[l] = min(T)
    ans = min(ans,sum(L)+k*x)

print(ans)

Submission status: Time Limit Exceeded

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

INF = float('inf')
dp = [[INF]*N for i in range(N+1)]
dp[0] = A[:]

ans = sum(A)
for k in range(N):
    cost = k*X
    if cost > ans: break
    for i in range(N):
        dp[k+1][i] = min(dp[k][i], A[i-k])
    cost += sum(dp[k+1])
    ans = min(ans, cost)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
a = [int(m) for m in input().split()]
#x=kのときを考える
#f(i,k)を考える，メモ化しておく
memos = []
for k in range(n):
    memos.append([float("INF") for i in range(n)])

def f(i,k):
    if k == 0:
        memos[k][i] = a[i]
        return a[i]
    if memos[k][i] != float("INF"):
        return memos[k][i]
    else:
        memos[k][i] = min(f(i, k - 1), a[i - k])
        return memos[k][i]

ansli = []
tmpsum = 0
for k in range(n):
    for i in range(n):
        tmpsum += f(i, k)
    ansli.append(x * k + tmpsum)
    tmpsum = 0

print(min(ansli))

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
a_list = list(map(int, input().split()))
ex_list = a_list.copy()
ex_list.extend(a_list)

ans = float("inf")
for i in range(N):
    cost = 0
    for j in range(N):
        cost += min(ex_list[N-i+j:N+1+j])

    cost += x * i
    ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

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

min_list = [[a[i] for i in range(n)] for _ in range(n)]
for i in range(1, n):
	for j in range(n):
		min_list[i][j] = min(min_list[i-1][j], a[(j-i) % n])

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

print(ans)

Submission status: Time Limit Exceeded

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

Ans = float("inf")
minA = [[None for i in range(N)] for j in range(N)]
minA[0] = A
Ans = sum(A) #全て直接捕まえる場合

for i in range(1, N): #i回魔法を唱える
    minA[i][0] = min(minA[i-1][0], A[-i])
    minAsum = minA[i][0]
    for j in range(1, N): #j番目のスライム用に捕まえるスライムの最小時間
        minA[i][j] = min(minA[i-1][j], A[j-i])
        minAsum += minA[i][j]
    Ans = min(Ans, i*x + minAsum)
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return [int(i) for i in input().split()]
import numpy as np
N, x = inpl()
a = np.array(inpl())
b = np.copy(a)
for i in range(N**2-N):
    if a[i%N]+x < a[(i+1)%N]:
        a[(i+1)%N] = a[i%N]+x
        b[(i+1)%N] = b[i%N]
print(np.max(a-b)+sum(b))

Submission status: Time Limit Exceeded

Solution code:
n,x = map(int,input().split())
a = list(map(int,input().split()))
MIN = sum(a)
tori = a + [0]
tori.pop()
for i in range(1,n):
  for j in range(n):
    ido = i+j
    if ido >= n:
      ido-=n
    tori[j] = min(a[ido],tori[j])
  MIN = min(sum(tori) + i*x,MIN)
print(MIN)

Submission status: Time Limit Exceeded

Solution code:
r=lambda :map(int,input().split())
n,x=r()
*a,=r()
dp=[[0]*n for _ in range(n)]
for i,j in enumerate(a):
  dp[0][i]=j
for i in range(1,n):
  for j in range(n):
    dp[i][j]=min(dp[i-1][j],a[(j-i)%n])
print(min(i*x+sum(j) for i,j in enumerate(dp)))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


N, x = inpl()
A = inpl()

min_index = A.index(min(A))
B = A[min_index:] + A[:min_index]

cost = [[INF] * N for i in range(N)]
for i in range(N):
    cost[i][0] = B[i]

for i in range(N):
    for magic in range(1, N):
        cost[i][magic] = min(cost[i][magic], min(B[max(0, i - magic)], cost[i][magic - 1]))

ans = INF
for magic in range(N):
    tmp = 0
    for i in range(N):
        tmp += cost[i][magic]
    ans = min(ans, tmp + magic * x)

print(ans)

Submission status: Time Limit Exceeded

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

memo = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    rec = -1
    for j in range(n):
        k = (n + i - j) % n
        if rec < 0 or a[k] < rec:
            rec = a[k]
        memo[i][j] = rec

record = -1
for j in range(n):
    temp = x*j
    for i in range(n):
        temp += memo[i][j]
    if record < 0 or temp < record:
        record = temp
        
print(record)

Submission status: Time Limit Exceeded

Solution code:
ai = lambda: list(map(int, input().split()))

n,x = ai()
a = ai()


def m(k):
    z = []
    for i in range(n):
        z.append(min(a[i-j] for j in range(k+1)))
    return sum(z)


print(min(m(k) + x*k for k in range(n)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

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

a = a+a

INF = float("inf")

# 区間内最小を探す
itv_min = [[INF for _ in range(2*n)] for _ in range(n)]
for st in range(n):
    mn = a[st]
    itv_min[st][st] = mn
    for ed in range(st+1,st+n):
        mn = min(mn, a[ed])
        itv_min[st][ed] = mn

# 魔法を唱える回数を固定
ans = INF
for k in range(n):
    temp = 0
    for st in range(n):
        temp += itv_min[st][st+k]
        
    ans = min(ans, temp+k*x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,x=map(int,input().split())
a=[int(i) for i in input().split()]
b=[[0 for k in range(N)] for i in range(N)]
for k in range(N):
    for i in range(N):
        if k==0:
            b[i][k]=a[i]
        else:
            b[i][k]=min([b[i][k-1],a[i-k]])
ans=sum(a)
for k in range(N):
    tmp=k*x
    for i in range(N):
        tmp+=b[i][k]
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X, A):

    ans = sys.maxsize
    mc = [(sys.maxsize, -1)] * N
    for k in range(N):
        ac = 0
        for i in range(N):
            mc[i] = min(mc[i], (A[i-k], k), key=lambda x: x[0])
            ac += A[i-mc[i][1]]
        ac += k*X
        ans = min(ans, ac)

    return ans


def main():
    N, X = read_int_n()
    A = read_int_n()
    print(slv(N, X, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, X = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

def solve(N, X, A):
    A2 = A + A
    T = [
        [min(A2[N+j+1-i-1:N+j+1]) for j in range(N)]
        for i in range(N)
    ]
    mins = [
        sum(T[i]) + i * X
        for i in range(N)
    ]
    result = min(mins)
    return result

print(solve(N, X, A))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

A=[int(x) for x in input().split()]

m=A.index(min(A))
A=A[m:]+A[:m]
dp=[[int(x) for x in A] for i in range(2)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

A=[int(x) for x in input().split()]
dp=[[float('inf') for x in range(N)] for y in range(N)]

#dp[0]=min(A)を捕まえる最短時間を調べる。
m=A.index(min(A))
A=A[m:]+A[:m]

#dp[i][j]=A[j]のスライムをi回魔法を唱えて捕まえるための最小時間。
#dp[0][0]=A[0],dp[0][1]=A[1],dp[0][2]=A[2]...で初期化。
for i in range(N):
  dp[0][i]=A[i]

#dp[1][1]=min(A[1],dp[0][0]),dp[1][2]=min(A[2],dp[0][1])...
#dp[i][j]=min(A[i],dp[i-1][j-1])
#最終的には回数ごとのsum+k*xの最小値が答え。
for i in range(1,N):
  for j in range(N):
    dp[i][j]=min(A[j],dp[i-1][j-1])

dp = [list(accumulate(x)) for x in dp]

ans=float('inf')
for i in range(N):
  ans=min(ans,dp[i][N-1]+i*x)

print(ans)

Submission status: Time Limit Exceeded

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

A=[int(x) for x in input().split()]
dp=[[float('inf') for x in range(N)] for y in range(N)]

#dp[0]=min(A)を捕まえる最短時間を調べる。
m=A.index(min(A))
A=A[m:]+A[:m]

#dp[i][j]=A[j]のスライムをi回魔法を唱えて捕まえるための最小時間。
#dp[0][0]=A[0],dp[0][1]=A[1],dp[0][2]=A[2]...で初期化。
for i in range(N):
  dp[0][i]=A[i]

#dp[1][1]=min(A[1],dp[0][0]),dp[1][2]=min(A[2],dp[0][1])...
#dp[i][j]=min(A[i],dp[i-1][j-1])
#最終的には回数ごとのsum+k*xの最小値が答え。
for i in range(1,N):
  for j in range(N):
    dp[i][j]=min(A[j],dp[i-1][j-1])

ans=float('inf')
for i in range(N):
  ans=min(ans,sum(dp[i])+i*x)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = float("INF")
b = [float("INF")]*N
for k in range(N):
    temp_ans = k*x
    for i in range(N):
        b[i] = min(b[i],a[i-k])
        temp_ans += b[i]
    ans = min(ans,temp_ans)
print(ans)

Submission status: Time Limit Exceeded

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

ans = float("INF")
b = np.full((N,N),np.inf)
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

print(int(ans))

Submission status: Time Limit Exceeded

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

ans = float("INF")
b = a
for k in range(N):
    c = [float("INF")]*N
    ans_inst = 0
    for i in range(N):
        c[i] = min(b[i],a[i-k])
        ans_inst += c[i]
    ans = min(ans, ans_inst+k*x)
    b = c
print(ans)