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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools,math,bisect,pprint,sys
n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
dp = a[:]
c = [0 for i in range(n)]
for i in range(n):
    if i<n-1:
        if dp[i]+x < dp[i+1]:
            c[i] += x
        dp[i+1] = min(dp[i]+x,dp[i+1])
    else:
        if dp[n-1]+x < dp[0]:
            c[0] += x
        dp[0] = min(dp[n-1]+x,dp[0])
print sum(dp)-sum(c)+max(c)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    N, x = (int(_) for _ in input().split(' '))
    As = [int(_) for _ in input().split(' ')]
    each = sum(As)
    change = N * x + N
    print(min(each, change))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N, x = ln()

A = ln()

result = 0
m_d_all = 0
for j in xrange(N):
    m = 1e10
    m_i = -1
    m_d = -1
    m_raw = 0
    for i in xrange(N):
        distance = j - i if j >= i else N - i + j
        cost = distance * x + A[i]
        if cost < m:
            m = cost
            m_i = j
            m_raw = A[i]
            m_d = distance
        if cost == m:
            m_d = min(distance, m_d)
    if m_d > m_d_all:
        m_d_all = m_d

    result += m_raw

print result + m_d_all * x

Submission status: Wrong Answer

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 = []
for idx in xrange(len(A)):
  C = []
  D.append([])
  for i in xrange(len(A)):
    print i
    if x*i >= A[idx]:
      break
    C.append(A[idx-i]+x*i)
    D[idx].append([A[idx-i],i])
  C = np.array(C)
  B[idx] = D[idx][np.where(C==min(C))[0][0]][0]
  E[idx] = D[idx][np.where(C==min(C))[0][0]][1]

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

Submission status: Wrong Answer

Solution code:
N, x = map(int, input().split())
a = list(map(int, input().split()))
t = 0
s = 0
for i in range(N):
	k = min(int(a[i] / x),N)
	for j in range(1,k+1):
		if a[i] > a[i-j] + x * j:
			a[i] = a[i-j]
			s = max(s, j)
t = sum(a) + s * x
print(t)

Submission status: Wrong Answer

Solution code:
n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
# print a
b = a[:]
m = min(a)
ma = 0
# print 'm', m
for j in xrange(n):
    for i in xrange(1,n):
        if a[j-i] + x*i < a[j]:
            if i > ma:
                ma = i
            b[j] = b[j-i]

print sum(b) + x * ma

Submission status: Wrong Answer

Solution code:
n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=0
for i in xrange(n):
    time=float('inf')
    for j in xrange(n):
        time=min(time,a[j]+min(abs(i-j),abs(n-j+i))*x)
    ans+=time
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=0
for i in xrange(n):
    time=float('inf')
    for j in xrange(n):
        time=min(time,a[j]+abs(i-j)*x)
    ans+=time
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
	N,x = map(int,raw_input().split())
	a = map(int,raw_input().split())
	total_cost = 0
	max_move = 0
	for i in xrange(N):
		gen_cost = a[i]
		for j in xrange(1,N):
			if a[(i-j)%N]+x*j < gen_cost:
				total_cost += a[(i-j)%N]
				if j > max_move: max_move = j
				break
		else:
			total_cost += gen_cost
	print total_cost + max_move*x
solve()

Submission status: Wrong Answer

Solution code:
a, b = map(int, raw_input().split())
b += 1
l = map(int, raw_input().split())

s = 0
for i in l:
	if i > b:
		s += b
	else:
		s += i

print s

Submission status: Wrong Answer

Solution code:
N, x = map(int, raw_input().split())
a = map(int, raw_input().split())
b = [None for i in xrange(N)]

ms = float('inf')
for i in xrange(N):
    s = 0
    md = 0
    for j in xrange(N):
        d = j - i if j >= i else j - i + N
        e = a[i] + x*d
        if e <= a[j]:
            s += a[i]
            if d > md:
                md = d
        else:
            s += a[j]
    if s+x*md < ms:
        ms = s+x*md
print ms

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N, x = ln()

A = ln()

result = 0
m_d_all = 0
for j in xrange(N):
    m = 1e10
    m_i = -1
    m_d = -1
    m_raw = 0
    for i in xrange(N):
        distance = j - i if j >= i else N - i + j
        cost = distance * x + A[i]
        if cost < m:
            m = cost
            m_i = j
            m_raw = A[i]
            m_d = distance
    if m_d > m_d_all:
        m_d_all = m_d

    result += m_raw

print result + m_d_all * x

Submission status: Wrong Answer

Solution code:
N, x = map(int, raw_input().split())
a = map(int, raw_input().split())
b = [None for i in xrange(N)]

ms = float('inf')
for i in xrange(N):
    s = 0
    for j in xrange(N):
        d = j - i if j >= i else j - i + N
        e = a[i] + x*d
        if e <= a[j]:
            s += e
        else:
            s += a[j]
    if s < ms:
        ms = s
print ms

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**9

def f():
    n,x = list(map(int, input().split()))
    a = list(map(int, input().split()))
    mi = a.index(min(a))
    a = a[mi:] + a[:mi]
    print("a",a)
    r = sum(a)
    for t in range(n-1):
        for i in range(n-1,0,-1):
            a[i] = min(a[i],a[i-1])
        tr = ((t+1)*x) + sum(a)
        if r > tr:
            r = tr
        else:
            break
    return r

print(f())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools,math,bisect,pprint,sys
n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
dp = a[:]
for i in range(n):
    if i<n-1:
        dp[i+1] = min(dp[i]+x,dp[i+1])
    else:
        dp[0] = min(dp[n-1]+x,dp[0])
print sum(dp)

Submission status: Time Limit Exceeded

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

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 cimport bool
from libcpp.vector cimport vector
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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
a1 = deepcopy(a)
for i in range(1, n):
    cur = x * i
    a2 = deepcopy(a1)
    for j in range(n):
        a1[n - j - 1] = min(a2[n - j - 1], a[n - i - j - 1])
        cur += a1[n - j - 1]
    ans = min(ans, cur)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 10**9

for i in range(n):
    tmp = a[(n-i) % n] + x*i
    for j in range(1, n):
        cost = 10**9
        for k in range(n):
            if k <= j:
                cost = min(cost, a[k]+x*max((j-k)-i, 0))
            else:
                cost = min(cost, a[k]+x*max(n-(k-j)-i, 0))
        tmp += cost
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    # identity element
    ide_ele = 10**9+1

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

    init(A)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class segtree:

    def __init__(self, n, operator, identity):
        """
        n:データ配列のサイズ
        operator:演算子(モノイド)。関数オブジェクト 最小=min, 最大=max
        identity:演算子に対応する単位元
        """
        nb = bin(n)[2:] #２進数に変換して先頭の0bを取り除く
        bc = sum([int(digit) for digit in nb]) #bitで1が立ってる数。これが1のときはちょうど2^nb.そうじゃないときは、2^nb<n<2^(nb+1)
        if bc == 1: #2^nbなら
            self.num_end_leaves = 2**(len(nb)-1) #最下段の葉っぱは2^nb個
        else:#そうじゃないなら2^(nb+1)確保
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #単位元で初期化

        self.identity = identity 
        self.operator = operator
        #後で使うので単位元と演算子を持っておく

    def update(self,x,val):
        """
        x:代入場所
        val:代入する値
        """
        actual_x = x+self.num_end_leaves #1-indexの末端の葉のindexがどこから始まるか分を足す(例えばデータ配列サイズ4のとき木配列サイズは8で、後半部はindex4から始まる。
        self.array[actual_x] = val #値を更新する
        while actual_x > 0 :
            actual_x = actual_x//2#親を見る
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#あたらしい子をつかって親を更新

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_left：クエリ区間の左
        q_right:クエリ区間の右
        arr_ind:木配列のインデックス。最初は親なので1
        leaf_left:木配列インデックスに対して、それが表す葉がカバーする範囲の左
        depth:木配列での深さ。カバー範囲の広さの計算に使用
        """
        width_of_floor = self.num_end_leaves//(2**depth) #今の葉のカバー幅
        leaf_right = leaf_left+width_of_floor-1 #左端とカバー幅から今の葉のカバー範囲の右を求める。

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #クエリ領域と葉が関係ないなら単位元を返す

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #クエリ領域に葉がすっぽり入ってるなら、葉の値を返す

        else: #そうじゃないならば、子を見る
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#子の左
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#子の右
            return self.operator(val_l,val_r)#子をマージする演算をする。

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
class segtree:

    def __init__(self, n, operator, identity):
        """
        n:データ配列のサイズ
        operator:演算子(モノイド)。関数オブジェクト 最小=min, 最大=max
        identity:演算子に対応する単位元
        """
        nb = bin(n)[2:] #２進数に変換して先頭の0bを取り除く
        bc = sum([int(digit) for digit in nb]) #bitで1が立ってる数。これが1のときはちょうど2^nb.そうじゃないときは、2^nb<n<2^(nb+1)
        if bc == 1: #2^nbなら
            self.num_end_leaves = 2**(len(nb)-1) #最下段の葉っぱは2^nb個
        else:#そうじゃないなら2^(nb+1)確保
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #単位元で初期化

        self.identity = identity 
        self.operator = operator
        #後で使うので単位元と演算子を持っておく

    def update(self,x,val):
        """
        x:代入場所
        val:代入する値
        """
        actual_x = x+self.num_end_leaves #1-indexの末端の葉のindexがどこから始まるか分を足す(例えばデータ配列サイズ4のとき木配列サイズは8で、後半部はindex4から始まる。
        self.array[actual_x] = val #値を更新する
        while actual_x > 0 :
            actual_x = actual_x//2#親を見る
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#あたらしい子をつかって親を更新

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_left：クエリ区間の左
        q_right:クエリ区間の右
        arr_ind:木配列のインデックス。最初は親なので1
        leaf_left:木配列インデックスに対して、それが表す葉がカバーする範囲の左
        depth:木配列での深さ。カバー範囲の広さの計算に使用
        """
        width_of_floor = self.num_end_leaves//(2**depth) #今の葉のカバー幅
        leaf_right = leaf_left+width_of_floor-1 #左端とカバー幅から今の葉のカバー範囲の右を求める。

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #クエリ領域と葉が関係ないなら単位元を返す

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #クエリ領域に葉がすっぽり入ってるなら、葉の値を返す

        else: #そうじゃないならば、子を見る
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#子の左
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#子の右
            return self.operator(val_l,val_r)#子をマージする演算をする。

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

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

arr += arr

for i,a in enumerate(arr):
    s_tree.update(i,a)

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