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

ans = 10**9 * 2001
for i in range(n):
    t = 0
    for j in range(n):
        tt = a[j]
        for k in range(j-i, j):
            tt = min(tt, a[k])
        t += tt
    t += x*i
    ans = min(ans, t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, raw_input().split())
A = map(int, raw_input().split())*2
ans = 10**18
for l in xrange(1, n+1):
    deq = [0]*(2*n)
    s = t = 0
    res = 0
    for i in xrange(n):
        while s<t and A[deq[t-1]] >= A[i]:
            t -= 1
        deq[t] = i
        t += 1
        if deq[s] == i-l+1:
            s += 1
    for i in xrange(n, 2*n):
        while s<t and A[deq[t-1]] >= A[i]:
            t -= 1
        deq[t] = i
        t += 1

        res += A[deq[s]]

        if deq[s] == i-l+1:
            s += 1
    ans = min(ans, res+x*(l-1))
print ans

Submission status: Time Limit Exceeded

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

if max(a) <= x:
    print sum(a)
else:
    flg = a <= x
    t = sum(a[flg])
    flg = np.roll(flg, 1)
    t += x
    
    while (flg == False).sum() > 0:
        ndx = np.where(flg == False)[0]
        i = np.argmin(a[ndx])
        if a[i] <= x:
            t += a[i]
            flg[i] = True
        else:
            t += x
            flg = np.roll(flg, 1)

    print t

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, raw_input().split())
A = map(int, raw_input().split())*2
ans = 10**18
for l in xrange(1, n+1):
    deq = []
    s = t = 0
    res = 0
    for i in xrange(n):
        while s<t and A[deq[t-1]] >= A[i]:
            deq.pop()
            t -= 1
        deq.append(i)
        t += 1
        #print i, l, A[deq[s]], deq[s:t]
        if deq[s] == i-l+1:
            s += 1
    for i in xrange(n, 2*n):
        while s<t and A[deq[t-1]] >= A[i]:
            deq.pop()
            t -= 1
        deq.append(i)
        t += 1

        res += A[deq[s]]
        #print i, l, A[deq[s]], deq[s:t], deq

        if deq[s] == i-l+1:
            s += 1
    ans = min(ans, res+x*(l-1))
print ans

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 = np.zeros(N)
E = np.zeros(N)
D = np.zeros((N,N))
F = np.zeros((N,N))
C = 10000000000*np.ones((N,N))
for idx in xrange(N):
  C[idx] = np.array([A[idx-i]+x*i for i in xrange(N)])
  D[idx] = np.array([A[idx-i] for i in xrange(N)])
  F[idx] = np.array(range(N))
  B[idx] = D[idx][np.where(C[idx]==min(C[idx]))[0][0]]
  E[idx] = F[idx][np.where(C[idx]==min(C[idx]))[0][0]]

print int(sum(B)+max(E)*x)

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 < (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:
def cast(curr, num):
    arr = [(x+num) % N for x in curr]
    return arr


def transform(curr, val):
    ret = 0
    while ((val-ret + N) % N) in curr:
        ret += 1
    return ret

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

curr = []
ans = 0
while len(curr) < N:
    cost = list(a)
    t = map(lambda x: transform(curr, x), range(N))
    for i in range(N):
        cost[i] += t[i] * x
    pick = cost.index(min(cost))
    curr = cast(curr, t[pick])
    ans += cost[pick]
    curr.append(pick)

print ans

Submission status: Time Limit Exceeded

Solution code:
def cast(curr, num):
    arr = [(x+num) % N for x in curr]
    return arr

def transform(curr, val):
    ret = 0
    temp = list(curr)
    while val in temp:
        temp = cast(temp, 1)
        ret += 1
    return ret

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

curr = []
ans = 0
while len(curr) < N:
    cost = list(a)
    t = map(lambda x: transform(curr, x), range(N))
    for i in range(N):
        cost[i] += t[i] * x
    pick = cost.index(min(cost))
    curr = cast(curr, t[pick])
    ans += cost[pick]
    curr.append(pick)

print ans

Submission status: Time Limit Exceeded

Solution code:
line=input().split()
n=int(line[0])
x=int(line[1])
a=input().split()
for i in range(n):
    a[i]=int(a[i])

costs=[]
for i in range (n):
    costs.append([a[i]])
    best=a[i]
    for j in range(1,n):
        best=min(best,a[i-j])
        costs[i].append(best)
best=2000*10**9
for j in range (n):
    curr=j*x
    if (curr>=best-n):
        pass
    else:
        for i in range (n):
            curr+=costs[i][j]
        best=min(best,curr)

print (best)

Submission status: Time Limit Exceeded

Solution code:
n, x = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
maxcnt = 0
sumget = 0

for a in range(n):
    _, cnt, get = min([(A[(a + n - i) % n] + i * x, i, A[(a + n - i) % n]) for i in range(n)])
    maxcnt = max(cnt, maxcnt)
    sumget += get

print(x * maxcnt + sumget)

Submission status: Time Limit Exceeded

Solution code:
line=input().split()
n=int(line[0])
x=int(line[1])
a=input().split()
for i in range(n):
    a[i]=int(a[i])
a.extend(a)

costs={}
for i in range (n,2*n):
    costs[i-n]=[a[i]]
    best=a[i]
    for j in range(1,n):
        best=min(best,a[i-j])
        costs[i-n].append(best)
best=2000*10**9
for j in range (n):
    curr=j*x
    for i in range (n):
        curr+=costs[i][j]
    best=min(best,curr)

print (best)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)



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

st = SegTree(al, min, 10**18)
ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = i*x
    for j in range(n): # ind
        l = j-i
        if l >= 0:
            amin = st.query(l,j+1)
        else:
            amin1 = st.query(0,j+1)
            amin2 = st.query(l+n,n)
            amin = min(amin1,amin2)
        curr_i_ans += amin
    ans = min(ans, curr_i_ans) 
print(ans)

Submission status: Accepted

Solution code:
class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

N,x = map(int,input().split()); INF = float("inf")
A = list(map(int,input().split()))
A = A+A
Tree = SegmentTree(A, min, INF)
ans = INF
for kaisu in range(N):
  temp = kaisu*x
  for i in range(N):
    right = 2*N-i
    left = right - (kaisu+1)
    temp += Tree.sum(left, right)
  ans = min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,x = MI()
A = LI()
B = deepcopy(A)
A += A

ans = sum(B)
for k in range(1,N+1):  # 魔法を k 回唱える
    for i in range(N):
        B[i] = min(B[i],A[N+i-k])
    ans = min(ans,sum(B)+k*x)

print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,x = MI()
A = LI()
B = deepcopy(A)
A += A

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

print(ans)

Submission status: Accepted

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

costs = al[:]
curr_sums = sum(costs)

# curr_mins = al[:]
curr_mins = al[:]

ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = 0
    for j in range(n): # ind
        ind = j-i
        if ind < 0: ind+=n
        # xcost = i*x
        next_a = al[ind]
        if curr_mins[j] > next_a:
            curr_mins[j] = next_a
        cost = curr_mins[j]
        curr_i_ans += cost
    ans = min(ans, curr_i_ans+i*x)

print(ans)

Submission status: Accepted

Solution code:
class SegmentTree():
  def __init__(self, n, oper, e):
    self.n = n
    self.oper = oper
    self.e = e
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [e] * (2 * self.size)

  def update(self, k):
    self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

  def build(self, arr):
    #assert len(arr) <= self.n
    for i in range(self.n):
      self.data[self.size + i] = arr[i]
    for i in range(self.size-1,0,-1):
      self.update(i)

  def prod(self, l, r):
    #assert 0 <= l <= r <= self.n
    sml = smr = self.e
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        sml = self.oper(sml, self.data[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.oper(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.oper(sml, smr)

import sys
input = sys.stdin.readline

N, x = map(int, input().split())
A = list(map(int, input().split()))
INF = float('inf')
st = SegmentTree(N,min,INF)
st.build(A)
ans = INF
for k in range(N):
  score = 0
  for j in range(N):
    if j-k>=0:
      score += st.prod(j-k, j+1)
    else:
      score += min(st.prod(0, j+1),st.prod((j-k)%N,N))
  ans = min(ans, k*x+score)
print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
INF = float('inf')
cum = [[INF]*N for _ in range(N)]
for i in range(N):
  for j in range(i,N):
    cum[i][j] = min(cum[i][j-1],A[j])
ans = INF
for k in range(N):
  score = 0
  for j in range(N):
    if j-k>=0:
      score += cum[j-k][j]
    else:
      score += min(cum[0][j],cum[(j-k)%N][-1])
  ans = min(ans, k*x+score)
print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
INF = (1<<42)-1
cum = [[INF]*N for _ in range(N)]
for i in range(N):
  for j in range(i,N):
    cum[i][j] = min(cum[i][j-1],A[j])
ans = INF
for k in range(N):
  score = 0
  for j in range(N):
    if j-k>=0:
      score += cum[j-k][j]
    else:
      score += min(cum[0][j],cum[(j-k)%N][-1])
  ans = min(ans, k*x+score)
print(ans)

Submission status: Accepted

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

val = A[:]
ans = 10 ** 18

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

print(ans)

Submission status: Accepted

Solution code:
header_code = """
#include "/opt/ac-library/atcoder/internal_bit.hpp"
#include "/opt/ac-library/atcoder/lazysegtree.hpp"
#include "/opt/ac-library/atcoder/modint.hpp"
#include <vector>
#include <algorithm>
#include <cassert>

namespace aclython {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = atcoder::internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l, S b) {
        return max_right(l, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int max_right(int l, S b, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]), b)) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]), b)) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r, S b) {
        return min_left(r, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int min_left(int r, S b, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm), b)) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm), b)) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};



int min_op(int n, int m){
    return std::min(n, m);
}

int min_e(){
    return (int)1e9;
}

struct segtree_min {
    public:
        segtree_min() : segtree_min(0) {}
        segtree_min(int n) : segtree_min(std::vector<int>(n, min_e())) {}
        segtree_min(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, min_op, min_e> seg;
};

int max_op(int n, int m){
    return std::max(n, m);
}

int max_e(){
    return 0;
}

struct segtree_max {
    public:
        segtree_max() : segtree_max(0) {}
        segtree_max(int n) : segtree_max(std::vector<int>(n, max_e())) {}
        segtree_max(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, max_op, max_e> seg;
};

using mint = atcoder::modint998244353;

struct S {
    mint a;
    int size;
    S(mint _a, int _size) : a(_a) ,size(_size) {}
    S(int _a, int _size) : a(_a) ,size(_size) {}
    S(const S &s) : a(s.a), size(s.size) {}
    int get_a() { return (int)a.val(); }
};

struct F {
    mint a, b;
    F(mint _a, mint _b) : a(_a), b(_b) {}
    F(int _a, int _b) : a(_a), b(_b) {}
    F(const F &f) : a(f.a), b(f.b) {}
    int get_a() { return (int)a.val(); }
    int get_b() { return (int)b.val(); }
};

S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }

S e() { return S{0, 0}; }

S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }

F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }

F id() { return F{1, 0}; }

struct lazy_segtree{
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& vec) : seg(vec) {}
    void set(int p, S x) { seg.set(p, x); }
    S get(int p) { return seg.get(p); }
    S prod(int l, int r) { return seg.prod(l, r); }
    S all_prod() { return seg.all_prod(); }
    void apply(int p, F f) { seg.apply(p, f); }
    void apply(int l, int r, F f) { seg.apply(l, r, f); }
    private:
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg;
};

}
"""

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/ac-library]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.string cimport string
from libc.stdio cimport getchar, printf
from libcpp.vector cimport vector
from libcpp cimport bool
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_min:
        segtree_min(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMin:
    cdef segtree_min *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_min(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_max:
        segtree_max(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMax:
    cdef segtree_max *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_max(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)


def SegTree(v, op):
    if op=="min":
        return SegTreeMin(v)
    elif op=="max":
        return SegTreeMax(v)

cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass S:
        S(int, int)
        S(S &)
        int get_a()
        int size
    cdef cppclass F:
        F(int, int)
        F(F &)
        int get_a()
        int get_b()
    cdef cppclass lazy_segtree:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)

cdef class LazySegTree:
    cdef lazy_segtree *_thisptr
    def __cinit__(self, vector[vector[int]] v):
        cdef int n = v.size()
        cdef vector[S] *sv = new vector[S]()
        cdef S *s
        for i in range(n):
            s = new S(v.at(i).at(0), v.at(i).at(1))
            sv.push_back(s[0])
        self._thisptr = new lazy_segtree(sv[0])
    cpdef void set(self, int p, vector[int] v):
        cdef S *s = new S(v.at(0), v.at(1))
        self._thisptr.set(p, s[0])
    cpdef vector[int] get(self, int p):
        cdef S *s = new S(self._thisptr.get(p))
        cdef vector[int] *v = new vector[int]()
        v.push_back(s.get_a())
        v.push_back(s.size)
        return v[0]
    cpdef vector[int] prod(self, int l, int r):
        cdef S *s = new S(self._thisptr.prod(l, r))
        cdef vector[int] *v = new vector[int]()
        v.push_back(s.get_a())
        v.push_back(s.size)
        return v[0]
    cpdef vector[int] all_prod(self):
        cdef S *s = new S(self._thisptr.all_prod())
        cdef vector[int] *v = new vector[int]()
        v.push_back(s.get_a())
        v.push_back(s.size)
        return v[0]
    cpdef void apply(self, int p, vector[int] v):
        cdef F *f = new F(v.at(0), v.at(1))
        self._thisptr.apply(p, f[0])
    cpdef void apply_range(self, int l, int r, vector[int] v):
        cdef F *f = new F(v.at(0), v.at(1))
        self._thisptr.apply(l, r, f[0])
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import SegTree, ReadInt

def main():
    N,x = ReadInt(2)
    A = ReadInt(N)
    ST = SegTree(A,"min")
    ans = 10**27
    for i in range(N):
        t = 0
        for j in range(N):
            if j-i<0:
                t += min(ST.prod(0,j+1),ST.prod(N+j-i,N))
            else:
                t += ST.prod(j-i,j+1)

        ans = min(t+i*x,ans)

    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def segfunc(x,y):return min(x,y)
ide_ele=10**18
class segtree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,x=map(int,input().split())
a=list(map(int,input().split()))
a+=a
st=segtree(a,segfunc,ide_ele)
ans=10**18
for k in range(n):
  cnt=k*x
  for i in range(n):
    cnt+=st.query(i,i+k)
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, x = map(int, input().split())
cost = np.fromstring(input(), dtype=np.int64, sep=' ')

ans = 10 ** 18
for i in range(N):  # i: 色の変更を行う回数
    ans = min(ans, sum(cost) + i * x)
    new_cost = np.empty_like(cost)
    new_cost[1:] = cost[:-1]
    new_cost[0] = cost[-1]
    new_cost = np.minimum(new_cost, cost)
    cost = new_cost

print(ans)

Submission status: Accepted

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

D = [a[i] for i in range(N)]
ans = sum(D)

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

print(ans)

Submission status: Accepted

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

ans = 10**9 * n
for i in range(n):
    ans = min(ans,sum(a[1:])+i*x)
    for j in range(n,0,-1):
        a[j] = min(a[j],a[j-1])
    a[0] = a[-1]
print(ans)

Submission status: Accepted

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

INF = 10**18

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        # set_val
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        # built
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])

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

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

def main():

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

    seg = SegTree(A, INF, min)
    ans = INF
    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()