Problem:

 

引越し

太郎君は引っ越しをすることになりました。太郎君はたくさんの荷物を持っているので、荷物の運搬を引っ越し業者に頼むことにしました。荷物はいろいろな重さの物があるので、わかりやすいように軽い方から順番に並べて置いてもらうように頼みましたが、引っ越し業者の人はばらばらの順番で荷物を置いていってしまいました。そこで太郎君は荷物を並べ替えようとしましたが、荷物は重いので運ぶのには体力が必要です。それぞれの荷物は今ある場所から他の荷物の間や荷物の端など好きな場所に運ぶことができますが、ある荷物を運ぶにはその荷物の重さと同じだけ体力を使います。太郎君はあまり体力がないので、できるだけ体力を使わずに荷物を軽い方から順番に並べる方法を考えることにしました。

Input

n
x1 x2 ... xn

nは太郎君の持っている荷物の数を表す

x1からxnはそれぞれの荷物の重さを表し、現在はx1、x2、…、xnの順に並んでいる

Constraints

1 ≤ n ≤ 105
1 ≤ xi ≤ n (1 ≤ i ≤ n)
xi &ne; xj (1 ≤ i, j ≤ n かつ i &ne; j)

入力はすべて整数で与えられる

Output

S

荷物を軽い方から順番に並べるのに必要な最小の体力の合計Sを出力せよ、ただし最後に改行を出力せよ

Sample Input 1

4
1 4 2 3

Output for the Sample Input 1

4

重さ4の荷物を右端に運ぶと重さの軽い順になります

Sample Input 2

5
1 5 3 2 4

Output for the Sample Input 2

7

重さ2の荷物を重さ1の荷物の右側に運び、重さ5の荷物を右端に運ぶと重さの軽い順になります

Sample Input 3

7
1 2 3 4 5 6 7

Output for the Sample Input 3

0

最初から重さの軽い順に並んでいます

Sample Input 4

8
6 2 1 3 8 5 4 7

Output for the Sample Input 4

19



Sample input:
4
1 4 2 3


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n = int(input())
    A = map(int, input().split())
    W = [0] * (n + 1)
    for a_i in A:
        W[a_i] = max(W[:a_i]) + a_i
    ans = n * (n + 1) // 2 - max(W)
    print(ans)

solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# segment tree
class SegmentTree:
    def _max(self,a,b):
        if a < b:
            return b
        else:
            return a

    def __init__(self,n):
        self.N = 1
        while(self.N < n):
            self.N *= 2
        self.seg = [0] * (self.N * 2 -1)

    def max_update(self,k,a):
        k += self.N - 1
        self.seg[k] = a

        while(0 < k):
            k = (k-1)//2;
            self.seg[k] = self._max(self.seg[2*k +1], self.seg[2*k + 2])

    def _max_query(self,a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self._max_query(a, b, k * 2 + 1, l, (l + r)//2)
            vr = self._max_query(a, b, k * 2 + 2, (l + r)//2, r)
            return self._max(vl,vr)

    def max_query(self,a, b):
        return self._max_query(a, b, 0, 0, self.N)

n = int(input())
X = list(map(int,input().split()))
st = SegmentTree(n+1)

for x in X:
    st.max_update(x, st.max_query(0,x) + x)
print((n * (n + 1))//2 - st.max_query(0,n+1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# st = SegmentTree(n, lambda a,b: a if a > b else b)
class SegmentTree:
    def __init__(self,n,f):
        self.N = 1
        self.f = f
        while(self.N < n):
            self.N *= 2
        self.seg = [0] * (self.N * 2 -1)

    def _update(self,k,a,f):
        k += self.N - 1
        self.seg[k] = a

        while(0 < k):
            k = (k-1)//2;
            self.seg[k] = self.f(self.seg[2*k +1], self.seg[2*k + 2])

    def _query(self,a, b, k, l, r,f):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self._query(a, b, k * 2 + 1, l, (l + r)//2,f)
            vr = self._query(a, b, k * 2 + 2, (l + r)//2, r,f)
            return self.f(vl,vr)
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N, self.f)
    
    def update(self, k ,a):
        return self._update(k, a, self.f)

n = int(input())
X = list(map(int,input().split()))
st = SegmentTree(n+1, lambda a,b: a if b < a else b)

for x in X:
    st.update(x, st.query(0,x) + x)
print((n * (n + 1))//2 - st.query(0,n+1))

Submission status: Accepted

Solution code:
import math


class RangeMaximumQuery:
    """
    RangeMaximumQuery by Segment Tree
    query:
    1. update(i, val): update i-th value to val
    2. query(low, high): find maximun value in [low, high)
    time complexity: O(log n)
    space complexity: O(2n)
    """
    def __init__(self, N, zero=0):
        self.N = 1 << math.ceil(math.log(N, 2))
        self.zero = zero
        self.segtree = [self.zero] * (self.N * 2 - 1)

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.segtree[i] = max(self.segtree[2*i+1], self.segtree[2*i+2])

    def query(self, low, high, k=0, left=0, right=-1):
        if right == -1:
            right = self.N
        if right <= low or high <= left:
            return self.zero

        if low <= left and right <= high:
            return self.segtree[k]
        else:
            mid = (left + right) // 2
            return max(self.query(low, high, 2*k+1, left, mid),
                       self.query(low, high, 2*k+2, mid, right))

N = int(input())
X = [int(x) for x in input().split()]
dp = RangeMaximumQuery(N)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(0, i) + x)
print(N * (N + 1) // 2 - dp.query(0, N))

Submission status: Accepted

Solution code:
import math


class SegmentTree:
    """
    Segment Tree
    query:
    1. update(i, val): update i-th value to val
    2. query(low, high): find f(value) in [low, high)
    time complexity: O(log n)
    space complexity: O(2n)
    """
    def __init__(self, N, f, default):
        self.N = 1 << math.ceil(math.log(N, 2))
        self.default = default
        self.f = f
        self.segtree = [self.default] * (self.N * 2 - 1)

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.segtree[i] = self.f(self.segtree[2*i+1], self.segtree[2*i+2])

    def query(self, low, high, k=0, left=0, right=-1):
        if right == -1:
            right = self.N
        if right <= low or high <= left:
            return self.default

        if low <= left and right <= high:
            return self.segtree[k]
        else:
            mid = (left + right) // 2
            return self.f(self.query(low, high, 2*k+1, left, mid),
                          self.query(low, high, 2*k+2, mid, right))


N = int(input())
X = [int(x) for x in input().split()]
dp = SegmentTree(N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(0, i) + x)
print(N * (N + 1) // 2 - dp.query(0, N))

Submission status: Accepted

Solution code:
import math


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << (math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(i) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))

Submission status: Accepted

Solution code:
import math
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << int(math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(i) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))

Submission status: Accepted

Solution code:
import math
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << int(math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x in X:
    dp.update(x - 1, dp.query(x - 1) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))

Submission status: Accepted

Solution code:
class RangeMaximumQuery:
    def __init__(self, n):
        self.size = n
        self.dat = [0] * (2 * n - 1)
    
    def update(self, i, x):
        i += self.size - 1
        self.dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            d1 = self.dat[i * 2 + 1]
            d2 = self.dat[i * 2 + 2]
            if d1 > d2:
                self.dat[i] = d1
            else:
                self.dat[i] = d2
    
    def getmax(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.getmax(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.getmax(a, b, k * 2 + 2, (l + r) // 2, r)
            if vl > vr:
                return vl
            else:
                return vr

def solve():
    from math import ceil, log
    
    n = int(input())
    A = map(int, input().split())
    s = 2 ** ceil(log(n, 2))
    W = RangeMaximumQuery(s)
    for a_i in A:
        cost = W.getmax(0, a_i - 1, 0, 0, s) + a_i
        W.update(a_i - 1, cost)
    ans = n * (n + 1) // 2 - W.getmax(0, n, 0, 0, s)
    print(ans)

solve()

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    dp = [0] * (n + 1)
    
    def update(i, x):
        while i <= n:
            if dp[i] < x:
                dp[i] = x
            i += i & -i
    
    def get_sum(i):
        s = 0
        while i > 0:
            t = dp[i]
            if s < t:
                s = t
            i -= i & -i
        return s
    
    A = map(int, input().split())
    
    for a_i in A:
        update(a_i, get_sum(a_i - 1) + a_i)
    
    ans = n * (n + 1) // 2 - get_sum(n)
    print(ans)

solve()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    *A, = map(int, input().split())

    data = [0]*(N+1)
    def update(k, x):
        while k <= N:
            data[k] = max(data[k], x)
            k += k & -k
    def get(k):
        s = 0
        while k:
            s = max(s, data[k])
            k -= k & -k
        return s

    B = [0]*N
    for i in range(N):
        B[A[i]-1] = i

    ans = 0
    for i in range(N):
        j = B[i]
        v = get(j+1)
        update(j+1, v+i+1)
    print(N*(N+1)//2 - get(N))
solve()

Submission status: Accepted

Solution code:
class RMQ:
    inf = 0
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.st = [self.inf]*(2*self.n-1)
    
    def update(self,k,x):
        k+=(self.n-1)
        self.st[k] = x
        while k >0:
            k = (k-1)//2
            self.st[k] = max(self.st[2*k+1],self.st[2*k+2])

    def search(self,a,b,k,l,r):
        if r<=a or b<=l :return self.inf
        if a<=l and r<=b:return self.st[k]
        L = self.search(a,b,k*2+1,l,(l+r)//2)
        R = self.search(a,b,k*2+2,(l+r)//2,r)
        return max(L,R)

    def query(self,a,b):
        return self.search(a,b,0,0,self.n)

n = int(input())
x = list(map(int,input().split()))
rmq = RMQ(n+1)
for i in x:
    res = rmq.query(1,i)
    rmq.update(i,i+res)
print (sum(x)-rmq.query(1,n+1))

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    rr = []

    def f(n):
        a = LI()
        seg = Seg(n, 0, max)
        for c in a:
            t = seg.query(0,c)
            seg.update(c, t+c)
        r = sum(a) - seg.total()
        return r

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        break

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
import math
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << (math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(i) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))