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 = [int(x) for x in input().split()]
b = [None] * n
for i, c in enumerate(a):
    b[i] = [None] * n
    b[i][0] = a[i]
    for j in range(1, n): b[i][j] = min(b[i][j - 1], a[(i - j) % n])
d = None
for i in range(n):
    c = i * x
    for j in range(n): c += b[j][i]
    if d is None or c < d: d = c
print(d)

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split())) * 2
A = A[::-1]

effective_costs = [float('inf')] * N
ans = float('inf')

# 魔法を使う回数
for k in range(N):
    cost = 0
    for i in range(N):
        effective_costs[i] = min(effective_costs[i], A[i+k])
        cost += effective_costs[i]
    ans = min(ans, cost + k * x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A[:]
ans = float('inf')

for k in range(N):
    cost = 0
    for i in range(N):
        lowest_costs[i] = min(lowest_costs[i], A[(i-k) % N])
        cost += lowest_costs[i]
    ans = min(cost + x * k, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A.copy()
A.extend(A)
ans = float('inf')

for k in range(N):
    cost = 0
    for i in range(N):
        lowest_costs[i] = min(lowest_costs[i], A[i+k])
        cost += lowest_costs[i]
    ans = min(cost + x * k, ans)

print(ans)

Submission status: Time Limit Exceeded

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

ans = float('inf')
for k in range(N):
    cost = 0
    for i in range(N):
        cost += min(A[i:i+k+1])
    ans = min(cost + x * k, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:


n, x = map(int, raw_input().split())
slimes = map(int, raw_input().split())

dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][0] = slimes[i]

best = sum(slimes)
for j in range(1, n):
    ans = 0
    for i in range(n):
        dp[i][j] = min(dp[i][j - 1], slimes[(i - j) % n])
        ans += dp[i][j]
    best = min(best, ans + j * x)
print best

Submission status: Time Limit Exceeded

Solution code:
n,x = map(int,input().split())
lis = list(map(int,input().split()))
ans = 0
magic = 0
for i in range(n):
    cou = lis[i]
    for m in range(1,n):
        if i + m >= n:co = i + m - n
        else:co = i + m
        cou = min(cou,lis[co]+x * max(m-magic,0))
        if cou == lis[co] + x * max(m-magic,0):magic = max(m,magic)
    ans += cou
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x = map(int,input().split())
lis = list(map(int,input().split()))
ans = 0
magic = 0
for i in range(n):
    cou = lis[i]
    for m in range(1,n):
        if i + m >= n:
            co = i + m - n
        else:
            co = i + m
        cou = min(cou,lis[co]+x * max(m-magic,0))
        if cou == lis[co] + x * max(m-magic,0):
            magic = max(m,magic)
    ans += cou
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
n = N
a = list(map(int, input().split()))
b = [[1000000000000000000000 for i in range(n)] for j in range(n)]
for i in range(n):
	b[i][0] = a[i]
	for j in range(1, n):
		b[i][j] = min(b[i][j-1], a[(i-j+n)%n])
s = [0 for i in range(n)]
for i in range(n):
	for j in range(n):
		s[j] += b[i][j]
ans = 1000000000000000000000
for i in range(n):
	for j in range(n):
		ans = min(ans, j*x+s[j])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

pos = a.index(min(a))
na = [a[pos]] + a[pos+1:] + a[:pos]

ans = sum(a)
for k in range(1, N):
    d = deque([], k + 1)
    b = []
    for i in range(N):
        d.append(na[i])
        # print(d)
        b.append(min(d))
    # print(k, b)
    ans = min(ans, k * x + sum(b))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())

###########

n,x=ii()
a=ii()
mi=[[0 for j in range(n)] for k in range(n)]
for s in range(n):
    mi[s][0]=a[s]
    for m in range(1,n):
        mi[s][m]=min(mi[s][m-1],a[(s-m)%n])
ans=INF
for m in range(n):
    cnt=x*m+sum([mi[s][m] for s in range(n)])
    ans=min(cnt,ans)

print ans

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())

###########

n,x=ii()
a=ii()
mi=[[0 for j in range(n)] for k in range(n)]
for s in range(n):
    mi[s][0]=a[s]
    for m in range(1,n):
        mi[s][m]=min(mi[s][m-1],a[(s-m)%n])
ans=INF
for m in range(n):
    cnt=x*m
    for s in range(n):
        cnt+=mi[s][m]
    ans=min(cnt,ans)

print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy


def solve(dp, collected_slimes, time_taken):
    if all_colour_picked(collected_slimes):
        return
    if dp[collected_slimes] < time_taken:
        return

    for i in range(n):
        if not collected_slimes[i]:
            collected_slimes_copy, new_time_taken = choose_new_slime(collected_slimes, i, time_taken)
            collected_slimes_copy2, new_time_taken2 = perform_magic(collected_slimes, time_taken)
            if new_time_taken < dp[collected_slimes_copy]:
                dp[collected_slimes_copy] = new_time_taken
            if new_time_taken2 < dp[collected_slimes_copy2]:
                dp[collected_slimes_copy2] = new_time_taken2
            solve(dp, collected_slimes_copy, new_time_taken)
            solve(dp, collected_slimes_copy2, new_time_taken2)


def all_colour_picked(collected_slimes):
    return all(item is True for item in collected_slimes)


def choose_new_slime(collected_slimes, num, time_taken):
    collected_slimes_copy = list(copy.deepcopy(collected_slimes))
    collected_slimes_copy[num] = True
    return tuple(collected_slimes_copy), time_taken + a[num]


def perform_magic(collected_slimes, time_taken):
    collected_slimes_copy2 = list(copy.deepcopy(collected_slimes))
    for i in range(n-1):
        collected_slimes_copy2[i] = collected_slimes[i + 1]
    collected_slimes_copy2[n-1] = collected_slimes[0]
    return tuple(collected_slimes_copy2), time_taken + x

if __name__ == '__main__':
    n, x = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    max_value = pow(10, 9) * 2000
    dp = defaultdict(lambda : max_value)
    collected_slimes = tuple([False for x in range(n)])
    solve(dp, collected_slimes, 0)
    for k, v in dp.items():
        if all(item is True for item in k):
            ans = v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, x = map(int, raw_input().split())
A = map(int, raw_input().split())

mincost = 0
costs = [[0]*N for _ in xrange(N)]
for i in xrange(N):
  costs[0][i] = A[i]
  mincost += A[i]

for i in xrange(1, N):
  tmpcost = 0
  for j in xrange(N):
    costs[i][j] = min(costs[i-1][j], A[(j-i) % N])
    tmpcost += costs[i][j]
  tmpcost += x * i
  if tmpcost < mincost:
    mincost = tmpcost

print mincost

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, input().split())
bs = list(map(int, input().split()))
dp1 = bs[:]
ans = sum(bs)
for k in range(1, 2000):
    dp2 = []
    for i, b in enumerate(bs):
        dp2.append(min(dp1[i-1], b))
    ans = min(ans, sum(dp2)+k*x)
    dp1 = dp2[:]
print(ans)

Submission status: Time Limit Exceeded

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

ans = sum(a)
b = a[:]
c = [0]*n

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))

Submission status: Time Limit Exceeded

Solution code:
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
ans = 0
b = []
for k in range(n):
    if k == 0:
        b = a.copy()
    else:
        for i in range(n):
            b[i] = min(a[(i-k)%n],b[i])
    cost = k*x+sum(b)
    if k == 0:
        ans = cost
    else:
        ans = min(ans,cost)
        if ans != cost:
            break
    if ans < (k+1)*x:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().strip().split(' ')))

n, x = mygets()
a = mygets()

b1 = a

ans = sum(a)

def f(k):
    u = k[1]
    v =  b1[(k[0] + n - 1) % n]
    if u < v:
        return u
    else:
        return v

for i in range(1, n):
    b2 = list(map(f, enumerate(a)))
    ans = min(ans, sum(b2) + i * x)
    b1 = b2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 0
b = []
for k in range(n):
    if k == 0:
        b = a[:]
    else:
        for i in range(n):
            b[i] = min(a[(i-k)%n],b[i])
    cost = k*x+sum(b)
    if k == 0:
        ans = cost
    else:
        ans = min(ans,cost)
        if ans != cost:
            break
    if ans < (k+1)*x:
        break
print ans

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
b = a[:]
ans = 0
for k in range(n):
    for i in range(n):
        b[i] = min(a[(i-k)%n],b[i])
    cost = k*x+sum(b)
    if k == 0:
        ans = cost
    else:
        ans = min(ans,cost)
        if ans != cost:
            break
    if ans < (k+1)*x:
        break
print ans

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    import sys
    return list(map(int, sys.stdin.readline().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

for i in range(1, n):
    for j, v in enumerate(a):
        b2[j] = min(v, b1[(j + n - 1) % n])
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

for i in range(1, n):
    for j, v in enumerate(a):
        b2[j] = min(v, b1[(j + n - 1) % n])
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().strip().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

for i in range(1, n):
    for j, v in enumerate(a):
        b2[j] = min(v, b1[(j + n - 1) % n])
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

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

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

xs = list(range(1, n))
ys = list(range(n))
ans = sum(a)

for i in xs:
    for j in ys:
        b2[j] = min(a[j], b1[(j + n - 1) % n])
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().strip().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

for i in range(1, n):
    for j in range(n):
        k = (j + n - 1) % n
        if a[j] < b1[k]:
            b2[j] = a[j]
        else:
            b2[j] = b1[k]
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().strip().split()))

def mymin(a, b):
    if a < b:
        return a
    else:
        return b

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

for i in range(1, n):
    for j in range(n):
        b2[j] = mymin(a[j], b1[(j + n - 1) % n])
    ans = mymin(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().strip().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

xt = 0
for _ in range(1, n):
    xt += x
    bsum = 0
    for j in range(n):
        b2[j] = min(a[j], b1[(j + n - 1) % n])
        bsum += b2[j]
    ans = min(ans, bsum + xt)
    b1, b2 = b2, b1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mygets():
    return list(map(int, input().strip().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a.copy()
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        s_cost[i] = min(s_cost[i], a[(i-k)%N])
    # s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( list(range(N)), list(range(N-k,N))+list(range(N-k)) )]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
for k in range(1,N):
    s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( list(range(N)), [(x-k)%N for x in list(range(N))]) ]
    # s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( list(range(N)), list(range(N-k,N))+list(range(N-k)) )]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)

Submission status: Time Limit Exceeded

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

b = [([0] * N)] * N
b[0] = list(a)
min_val = sum(b[0])
for i in range(1, N):
    for j in range(N):
        b[i][j] = min(b[i-1][j], a[j-i])
    if sum(b[i]) + i*x < min_val:
        min_val = sum(b[i]) + i*x

print min_val

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x = map(int, input().split())
arr = np.array(list(map(int,input().split())),int)
mat = np.zeros((n,n),int)
for i in range(n):
    for j in range(n):
        mat[i][(i+j)%n]=arr[i]+x*j
am = mat.argmin(0)
sum=0
for ix in am:
    sum+=arr[ix]
sum+=((am - np.array(range(n)))%n).max()*x
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

N, x = map(int,raw_input().split())
A = map(int,raw_input().split())

B = copy.deepcopy(np.array(A))
m = sum(B)
for idx in xrange(1,N):
  A.append(A[0])
  A.pop(0)
  np.fmin(B, A, out=B)
  m = min(sum(B)+idx*x, m)

print int(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

N, x = map(int,raw_input().split())
A = map(int,raw_input().split())

B = copy.deepcopy(A)
m = sum(B)
for idx in xrange(1,N):
  A = np.append(A, A[0])
  A = np.delete(A, 0)
  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)

Submission status: Time Limit Exceeded

Solution code:
import time
import numpy as np
import copy

tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = np.random.randint(m,size=(N))
  st = time.time()
else:
  a = map(int,raw_input().split())
  N = a[0]
  x = a[1]
  A = map(int,raw_input().split())

B = copy.deepcopy(A)
m = sum(B)
for idx in xrange(1,N):
  A = np.append(A, A[0])
  A = np.delete(A, 0)
  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)

Submission status: Time Limit Exceeded

Solution code:
import time
import numpy as np
import copy

tflag = True
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = np.random.randint(m,size=(N))
  st = time.time()
else:
  a = map(int,raw_input().split())
  N = a[0]
  x = a[1]
  A = map(int,raw_input().split())

B = copy.deepcopy(A)
m = sum(B)
for idx in xrange(1,N):
  A = np.append(A, A[0])
  A = np.delete(A, 0)
  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
a = map(int,raw_input().split())
N = a[0]
x = a[1]
A = map(int,raw_input().split())

B = [A]
m = sum(B[0])
for idx in xrange(1,N):
  B.append( [min(B[idx-1][i], A[i-idx]) for i in range(N)] )
  m = min(m, sum(B[idx])+idx*x)
 
print int(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = np.random.randint(m,size=(N))
#  st = time.time()
else:
  a = map(int,raw_input().split())
  N = a[0]
  x = a[1]
  A = map(int,raw_input().split())

E = np.zeros(N)
B = [A]
E[0] = sum(B[0])
for idx in xrange(1,N):
  B.append( [min(B[idx-1][i], A[i-idx]) for i in range(N)] )
  E[idx] = sum(B[idx])+idx*x

print int(min(E))

Submission status: Time Limit Exceeded

Solution code:
import math

N, x = map(int, raw_input().split())
A = map(int, raw_input().split())
ans = 1e18
b = [[ans for i in range(N)] for j 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+N-k)%N])
    sum = 0
    for i in range(N):
        sum += b[i][k]
    sum += k*x
    ans = min(ans, sum)
print ans

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a.copy()
cost = sum(s_cost)
orig_list = list(range(N))
index_list = orig_list.copy()
for k in range(1,N):
    index_list = [x-1 for x in index_list]
    index_list =  [x%N for x in index_list]
    s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( orig_list, index_list )]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
orig_list = list(range(N))
for k in range(1,N):
    s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( orig_list, list(range(N-k,N))+list(range(N-k)) )]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
for k in range(1,N):
    s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( list(range(N)), list(range(N-k,N))+list(range(N-k)) )]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
for k in range(0,N):
    s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( list(range(N)), list(range(N-k,N))+list(range(N-k)) )]
    if cost >= k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
        # cost = min(cost, k*x + sum(s_cost))
    else:
        break
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        i_index = i-k
        if (i-k) == -1:
            i_index+=N
        s_cost[i] = min(s_cost[i], s_cost[i_index])
    cost = min(cost, k*x + sum(s_cost))

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

@memoize
def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]
    
s=[0]*n
for k in range(n):
    s[k]=k*x
    for j in range(n):
        s[k]+=dp(j,k)

print min(s)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

@memoize
def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]
s=[0]*n
for k in range(n):
    s[k]=sum([dp(j,k) for j in range(n)])+k*x

print min(s)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

@memoize
def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]

print min([sum([dp(j,k) for j in range(n)])+k*x for k in range(n)])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]

print min([sum([dp(j,k) for j in range(n)])+k*x for k in range(n)])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = np.random.randint(m,size=(N))
#  st = time.time()
else:
  a = map(int,raw_input().split())
  N = a[0]
  x = a[1]
  A = map(int,raw_input().split())

E = np.zeros(N)
B = 1000000000*np.ones((N,N))
B[0] = np.array(A)
E[0] = sum(B[0])
for idx in xrange(1,N):
  B[idx] = np.array([min(B[idx-1][i], A[i-idx]) for i in range(N)])
  E[idx] = sum(B[idx])+idx*x

print int(min(E))

Submission status: Time Limit Exceeded

Solution code:
N, x = map(int, raw_input().split())
A = map(int, raw_input().split())
import numpy as np
 
count = 0
a = np.zeros([N,N])

A = np.array(A)
 
a[N-1][0] = A[N-1]
 
for i in range(N-1):
    a[i][0] = A[i]
    
    for j in range(N-1):
        a[i+1][j+1] = a[i][j] + x
    
for j in range(N-1):
    a[0][j+1] = a[N-1][j]
 
for i in range(N):
    count += min(a[i])
 
 
print int(count)