Problem:


Score : 500 points

Problem Statement

You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \}.
For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

If A_i and A_j (i < j) are painted with the same color, A_i < A_j.

Find the minimum number of colors required to satisfy the condition.

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the minimum number of colors required to satisfy the condition.

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
# print(N, A)

def solve(a, cur, nxt):
    for i in range(1, len(cur)):
        if cur[i] > a:
            a = cur[i]
        else:
            nxt.append(cur[i])

ans = 0
cur = A
nxt = []
while True:
    ans += 1
    a = cur[0]
    solve(a, cur, nxt)
    if len(nxt) == 0:
        break
    cur = nxt
    nxt = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
q = [A[0]]
p = A[0]
for i in range(1,N):
    if p >= A[i]:
        insert_index = bisect.bisect_left(q,A[i])
        if insert_index == 0:
            q = [A[i]] + q
            ans += 1
        else:
            q[insert_index-1] = A[i]
    else:
        insert_index = bisect.bisect_left(q,A[i])
        q[insert_index-1] = A[i]
    p = A[i]
print(len(q))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
while sum(A) != len(A)*(-1):
    ans += 1
    compare = -1
    for i,a in enumerate(A):
        if a != -1:
            if a > compare:
                compare = a
                A[i] = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
len_arr = int(input())

arr = [int(input()) for _ in range(0, len_arr)]

current_min = [arr[-1]]
num_color = 1

for i in reversed(range(0, len_arr-1)):
    target = arr[i]
    # print(current_min)

    if target >= max(current_min):
        num_color += 1
        current_min.append(target)
    else:
        acceptable = [x for x in current_min if x > target]
        selected = min(acceptable)
        current_min.remove(selected)
        current_min.append(target)

print(num_color)
exit(0)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
jud = [True for i in range(N)]
co = 0
s = A[:]
while s != []:
  co  += 1
  t = []
  for i in range(len(s)):
    if i == 0:
      k = s[0]
    else:
      if s[i] <= k:
        t.append(s[i])
      else:
        k = s[i]
  s = t[:]  
print(co)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

inf = float('inf')

n = int(input())
a = tuple(int(input()) for _ in range(n))

h = [inf]

cnt = 0
for aa in a:
    if aa <= h[0]:
        heappush(h, aa)
        cnt += 1
    else:
        s = []
        while True:
            v = heappop(h)
            if aa <= h[0]:
                heappush(h, aa)
                for ss in s:
                    heappush(h, ss)
                break
            else:
                s.append(v)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

b = [a[0]]
for i in range(n-1):
    if min(b) >= a[i+1]:
        b.append(a[i+1])
    else:
        j = 0
        while(True):
            if a[i+1] > b[j]:
                b[j] = a[i+1]
                break
            j += 1
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    g = []

    from bisect import bisect_left

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.append(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                g.insert(0, a)
    dprint(g)
    print(len(g))
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
left = 0
ans = 1
l = 1
pre = A[0]
right = 1
while len(A) > 1:
    if right >= len(A):
        A.pop(left)
        l = 1
        ans += 1
        right = left+1
        pre = A[left]
    elif pre < A[right]:
        l += 1
        pre = A.pop(right)
    else:
        right += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
C = 1
for a in A[1:]:
    b = 0 if a<=B[0] else bisect.bisect_left(B,a)
    if b==0:
        bisect.insort_left(B,a)
        C+=1
    else:
        B[b-1] = a
print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = [int(input()) for i in range(n)]
list = [-1]
count = 0
for i in s:
  flg = True
  for l in range(len(list)):
    if list[l] < i:
      list[l] = i
      flg = False
      break
  if flg:
    list.append(i)
    
print(len(list))

Submission status: Time Limit Exceeded

Solution code:
import math

def search(S):

    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    A.append(S)
    return



def main():
    N = int(input())
    A[0] = int(input())
    le = 1
    m = A[0]
    m_i = 1
    for _ in range(N-1):
        S = int(input())
        search(S)
    print(len(A))

    

if __name__ == "__main__":
    A = [0]
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = []
for i in range(n):
    aa = int(input())
    a.append(aa)

ans = [a[0]]

for i in range(1,n):
    ju = "no"
    for j in range(len(ans)):
        if ans[j] < a[i]:
            ans[j] = a[i]
            ju = "ok"
            break

    if ju == "no":
        ans.append(a[i])

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect


n = int(input())
lines = []
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.insert(0, a)
        continue
    
    lines[index - 1] = a

print(len(lines))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=[]
for i in range(n):
  a.append(int(input()))
ans=[a[0]]

import bisect
#print(ans,a)
for i in range(1,n):
  if a[i] <= ans[0]:
     ans = [a[i]] + ans
  else:
    j = bisect.bisect_left(ans,a[i])
    ans[j-1] = a[i] 

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
num = []
ids = [-1]*n
for i in range(n):
	num.append(int(input()))

ans = 1
while True:
	if -1 not in ids:
		break
	start = ids.index(-1)
	i = start
	ids[start] = ans
	while True:
		if i == len(num):
			ans += 1
			break
		if ids[i] != -1:
			i += 1
			continue
		else:
			if num[start] < num[i]:
				ids[i] = ids[start]
				start = i
				i += 1
				continue
			else:
				i += 1
				continue
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

Colors = []
Colors.append(A[0])

for i in range(1, N):
    if Colors[-1] >= A[i]:
        Colors.append(A[i])
    else:
        j = 0
        while True:
            if Colors[j] < A[i]:
                Colors[j] = A[i]
                break
            j += 1
print(len(Colors))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))

l=len(A)
Ans=0
while(l>0):
    tmp =[]
    a=A[0]
    tmp.append(0)
    l_tmp=1
    for i in range(l):
        if A[i]>a:
            a=A[i]
            tmp.append(i)
            l_tmp=l_tmp+1

    for i in range(l_tmp):
        A.pop(tmp.pop())

    l=len(A)
    Ans=Ans+1

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 1
l = [int(input())]
for _ in range(N-1):
    flag = False
    k = int(input())
    for i in range(len(l)):
        if k > l[i]:
            l[i] = k
            flag = True
            break
    if not flag:
        l.append(k)
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

C = [0] * N
c = 0
for i in range(N):
    if C[i] == 0:
        c += 1
        C[i] = c
        m = A[i]
        for j in range(i+1,N):
            if C[j] == 0:
                if A[j] > m:
                    C[j] = c
                    m = A[j]
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
sln = []


def update_solution(sln, k):
    ln = len(sln)
    if ln == 0 or k <= sln[0]:
        sln.insert(0, k)
        return

    for j in range(ln):
        if sln[ln - j - 1] < k:
            sln[ln - j - 1] = k
            break


for i in range(n):
    update_solution(sln, int(input()))

print(len(sln))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

ans = 0

while True:
    frg = 0
    n = len(a)
    _a = a.copy()
    _max = 10**9+1
    for i in range(n):
        if _a[n-1-i] < _max:
            _max = a.pop(n-1-i)
            frg = 1
    if frg == 1:
        ans += 1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
N = int(input())
A = [int(input()) for i in range(N)]
min_ = pow(10, 9)
C = [A[0]]
for a in A[1:]:
    if a <= min(C):
        C.append(a)
    else:
        for i, c in enumerate(C):
            if a > c:
                C[i] = a
                break
print(len(C))

Submission status: Time Limit Exceeded

Solution code:

def submit():
    n = int(input())

    colors = []

    t = int(input())
    colors.append([t])

    for i in range(n - 1):
        t = int(input())

        appended = False
        for cs in colors:
            if cs[-1] < t:
                cs.append(t)
                appended = True
                break

        if not appended:
            colors.append([t])

    print(len(colors))








if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
colored = [0]*N
for i in range(N):
    if colored[i] != 0:
        continue
    else:
        ans += 1
        tmp = A[i]
        colored[i] = ans
    for j in range(i+1, N):
        if A[j] > tmp and colored[j] == 0:
            colored[j] = ans
            tmp = A[j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_left
	
def LIS(L) :
    step = 0
    x = 0
    while True :
        for i in range(x, N) :
            if L[i] >= 0 :
                break
        else :
            break
            
        lis = [L[i]]
        pos = [i]
        x = i
        for p in range(i+1, N) :
            a = L[p]
            if a > lis[-1] :
                lis.append(a)
                pos.append(p)
            elif a >= 0 :
                s = bisect_left(lis, a)
                if lis[s] != a :
                    lis[s] = a
                    pos[s] = p
        # print(pos)
        for p in pos :
            L[p] = -1
        # print(L)
        step += 1
    return step

print(LIS(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = [int(input()) for _ in range(N)]

ans = 0
while A:
    ans += 1
    head = A[0]
    del A[0]
    length = len(A)
    i = 0
    while i < length:
        #print(A,head,A[i])
        if head < A[i]:
            head = A[i]
            #print("del",A[i])
            del A[i]
            length -= 1
        else:
            i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a1 = int(input())
    a.append(a1)
countc = 0
while len(a) > 0:
    count = len(a) - 1
    count1 = 0
    k = 1
    while count - count1 > 0:
        if a[count-1-count1] >= a[count]:
            count1 = count1 + 1
            k = 0
        else:
            del a[count]
            count = count - 1 - count1
            k = 1
    del a[count]
    countc = countc + 1
print(countc)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0 for i in range(N)]

color = 1
A[0] = int(input())

for i in range(N - 1):
        a = int(input())
        num = -1
        for j in range(color):
                if A[j] < a:
                        num = j + 1
                        A[j] = a
                        break

        if num == -1:
                A[color] = a
                color += 1

print(color)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

color = [float("inf")]
min_color = color[0]
for i in a:
    if i <= min_color:
        color = [i] + color
        min_color = i
    else:
        insert = bisect.bisect_left(color, i)
        color[insert - 1] = i
        if insert == 1:
            min_color = color[0]
print(len(color) - 1)

Submission status: Time Limit Exceeded

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

from copy import copy


def solve():
    N = int(input())
    A = []
    count = 0
    for _ in range(N):
        A.append(int(input()))
    while A:
        a = A.pop()
        count += 1
        B = []
        while A:
            b = A.pop()
            if b >= a:
                B.append(b)
                continue
            a = b
        A = B[::-1]
    return count
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
# n = 6
# a = [5,6,7,2,6,4]

b = [a[0]]
minb = a[0]
count = 1
for i in range(1,n):
    if minb < a[i]:
        for j in range(len(b)):
            if b[j] < a[i]:
                b[j] = a[i]
                minb = min(b)
                break
    else:
        b += [a[i]]
        count += 1
        minb = a[i]

print(count)

Submission status: Time Limit Exceeded

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


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        # 増分が一番小さいものを選ぶ
        for index, color in enumerate(color_list[:color_num + 1]):
            if color < a:
                color_list[index] = a
                if index == color_num:
                    color_num = color_num + 1
                break
        # color_list[:color_num + 1] = sorted(color_list[:color_num + 1], reverse=True)
        # print(color_list)
    # print()
    # print(color_list)
    print(color_num)

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for n in range(N)]

tree = [[A[0]]]
leaf = [A[0]]
for n in range(1,N):
    a = A[n]
    pos = min(n-1,bisect.bisect_left(leaf,a)-1)
    if pos==-1:
        tree.insert(0,[a])
        leaf.insert(0,a)
    else:
        tree[pos].append(a)
        leaf[pos] = a
print(len(tree))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
cnt=0
ans=0
used=[False]*n
while cnt<n:
    ans+=1
    mx = -1
    for i in range(n):
        if used[i]:continue
        if a[i]>mx:
            used[i]=True
            mx=a[i]
            cnt+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a_list = []
for i in range(N):
    a_list.append(int(input()))

b_list = [0]*N
c = 1
for i, a in enumerate(a_list):
    if b_list[i] != 0:
        continue
    else:
        max_a = a
        b_list[i] = c
        for j, b in enumerate(a_list[i+1:]):
            k = i + j + 1
            if b_list[k] != 0:
                continue
            else:
                if max_a < b:
                    b_list[k] = c
                    max_a = b
                else:
                    continue

        c += 1

print(len(set(b_list)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list=[]
ans_head=[-1]
for i in range(n):
  a=int(input())
  for j in range(len(ans_head)):
    if ans_head[j]<a:
      ans_head[j]=a
      break
    else:
      if j==len(ans_head)-1:
        ans_head.append(a)
print(len(ans_head))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
aa=[]
for i in range(n):
    aa.append(int(input()))
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[i])
    else:
        if bb[0] >= aa[i]:
            bb = [aa[i]] + bb
        else:
            for j in range(len(bb)):
                if bb[-(j+1)] < aa[i]:
                    bb[-(j+1)] = aa[i]
                    bb = sorted(bb)
                    break
print(len(bb))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
count = 0
for i in A:
    for j in A:
        if i < j:
            A.remove(j) 
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:

def bisect(a,B,lo,hi):
    if hi-lo<=1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

A = [int(input()) for i in range(N)]

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B)-1)]=A[i]
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
C = 1
for a in A[1:]:
    b = bisect.bisect_left(B,a)
    if b==0:
        B = B[:b]+[a]+B[b:]
        C+=1
    else:
        B[b-1] = a
print(C)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
B = [10 ** 9 + 1]
for i in range(N):
  A = int(input())
  flag = True
  for j in range(len(B)):
    if A > B[j]:
      B[j] = A
      flag = False
      break
  if flag:
    B.append(A)
    B.sort(reverse=True)
print(len(B) - 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = []
for i in range(n):
  inp = int(input())
  for i in range(len(lst)):
    if inp > lst[i][-1]:
      lst[i].append(inp)
      break
  else:
    lst.append([inp])
print(len(lst))

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = []
n = int(n)

for i in range(n):
    a.append(int(input()))

t = [[a[0]]]

for i in a[1:]:
    flg = 0
    for j, m in enumerate(t):
        if m[-1] < i:
            t[j].append(i)
            flg = 1
            break
    if flg == 0:
        t.append([i])

print(len(t))

Submission status: Time Limit Exceeded

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
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 DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

def solve():
    n = int(input())
    a = []
    
    col = 1

    for _ in range(n):
        a.append(int(input()))
    
    if n == 1:
        print(col)
        exit()

    b = [a[0]]

    for i in range(1,n):
        x = bisect_left(b,a[i])
        
        if x == 0:
            col += 1
            insort_left(b,a[i])
        else:
            b[x-1] = a[i]
            
    print(col)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right, insort_left
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []

ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        min_num = a
        ans += 1
    else:
        # idx = bisect_right(que, a-1)
        if a <= min_num:
        # if idx == 0:
            insort_left(que, a)
            ans += 1
            min_num = a
        else:
            idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    #print(que, min_num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
for a in A[1:]:
    for i,b in enumerate(B):
        if b<a:
            B[i] = a
            break
    else:
        B.append(a)
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
c = []
color = 0
for i in range(N):
    if(i == 0):
        c.append(a[0])
        color += 1
    else:
        if(a[i-1] < a[i]):
            c.append(a[i])
        elif(a[i-1] >= a[i]):
            flag = False
            for j in range(len(c)):
                if(c[j] < a[i]):
                    c[j] = a[i]
                    flag = True
                elif(flag == False and j == len(c)-1):
                    color += 1
                    c.append(a[i])
print(color)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for n in range(N):
    a=int(input())
    A.append(a)
c=0
for n in range(N):
    a=A[n]
    for i in range(n+1,N):
        if a<A[i]:
            a=A[i]
            A[i]=0
            c=c+1
print(N-c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input())]
for i in range(n-1):
    new=int(input())
    if a[-1]>=new:a.append(new)
    else:
        for j in range(len(a)):
            if a[j]<new:a[j]=new;break
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for x in range(N)]
count = 0
i = 0
while A != []:
    count += 1
    base = A[0]
    del A[0]
    i = 0
    while i < len(A):
        if A[i] > base:
            base = A[i]
            del A[i]
        else:
            i += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

if(N == 1):
    print(1)
else:
    color = 1
    right = A[N-1]
    left_list = [-1]
    for i in range(1, N):
        num = N-i-1
        if(A[num] >= right):
            max_left = max(left_list)
            if(A[num] >= max_left):
                color += 1
                left_list.append(right)
            else:
                left_list.pop(left_list.index(max_left))
                left_list.append(A[num])
        right = A[num]
    print(color)

Submission status: Time Limit Exceeded

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**10
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 _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

res = [] 
for a in A:
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[0]:
            # 小さいので追加
            res = [a] + res
        else:
            # 入れ替え
            p = bisect.bisect_left(res, a)
            res[p-1] = a
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input())
    a_list = []
    color_list = []
    for i in range(n):
        a = int(input())
        paint = False
        for idx, color in enumerate(color_list):
            if a > color:
                color_list[idx] = a
                paint = True
                break
        if paint == False:
            color_list.insert(0, a)

    print(len(color_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

from bisect import bisect_left, bisect_right  # 二分探索

def main():
    N = i2n()
    A = ii2nn(N)
    B = [-1]
    for a in A:
        t = bisect_left(B, a)
        if t > 0:
            B[t-1] = a
        else:
            B = [a] + B
    print(len(B))

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(input()) for i in range(n)]
d = {}

c = 1
for i in l:
    while True:
        if c not in d:
            d[c] = i
            break
        else:
            if i > d[c]:
                d[c] = i
                break
            else:
                c += 1             
    c = 1

print(len(d))

Submission status: Time Limit Exceeded

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


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        # 増分が一番小さいものを選ぶ
        for index, color in enumerate(color_list[:color_num + 1]):
            if color < a:
                color_list[index] = a
                if index == color_num:
                    color_num = color_num + 1
                break
        color_list[:color_num + 1] = sorted(color_list[:color_num + 1], reverse=True)
        # print(color_list)
    # print()
    # print(color_list)
    print(color_num)

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
sln = []


def update_solution(sln, k):
    ln = len(sln)
    sln.sort()
    if ln == 0 or k <= sln[0]:
        sln.append(k)
        return

    for j in range(ln):
        if sln[ln - j - 1] < k:
            sln[ln - j - 1] = k
            break


for i in range(n):
    update_solution(sln, int(input()))

print(len(sln))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
C = 1
for a in A[1:]:
    b = bisect.bisect_left(B,a)
    if b==0:
        bisect.insort_left(B,a)
        C+=1
    else:
        B[b-1] = a
print(C)

Submission status: Time Limit Exceeded

Solution code:

def bisect(a,B,lo,hi):
    if hi-lo==1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

A = [int(input()) for i in range(N)]

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B))]=A[i]
print(len(B))

Submission status: Time Limit Exceeded

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

N = int(input())
A = [None] * N
for i in range(N):
    A[i] = int(input())

max_list = [-1]
flag = False
for i in range(N):
    for idx, l in enumerate(max_list):
        if l < A[i]:
            max_list[idx] = A[i]
            flag = True
            break
    if not flag:
        max_list.append(A[i])
    flag = False

ans = len(max_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for _ in range(N):
  A.append(int(input()))
K=[]
for i in range(N):
    if i==0:
        K.append(A[0])
    else:
        for j in range(len(K)):
            if A[i]>K[j]:
                K[j]=A[i]
                break
        else:
            K.append(A[i])

print(len(K))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alist = [int(input()) for _ in range(n)]
used = [0 for _ in range(n)]

st_index = 0
st_val = 0
num_color = 0
while sum(used) < n:
    for i, u in enumerate(used):
        if not u:
            st_index = i
            break
    st_val = alist[st_index]
    used[st_index] = 1
    num_color += 1
    while True:
        d_min = 10**9 + 1
        d_i = st_index
        for i in range(st_index, n):
            if used[i] > 0:
                continue
            diff = alist[i] - st_val
            if 0 < diff < d_min:
                d_min = diff
                d_i = i
        if d_i > st_index:
            st_index = d_i
            st_val = alist[st_index]
            used[st_index] = 1
        else:
            break

print(num_color)