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:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from operator import itemgetter, mul
from copy import deepcopy,copy
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n=INT()
    a = [INT() for _ in range(n)]

    lis=[]
    clr=1
    clr_lis=[]


    for i in range(n-1):
        if lis==[]:
            if a[i+1] <= a[i]:
                lis.append(a[i])
                clr+=1

        else:
            if a[i+1] <= a[i]:
                lis.sort()
                if a[i+1] <= lis[0]:
                    lis.append(a[i])
                    clr+=1
                else:
                    lis.sort()
                    lis.pop(0)
                    lis.append(a[i+1])


    
    #print(lis)
    print(clr)

if  __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

li =[a[0]]
for i in range(1, n):
    if a[i] <= li[-1]:
        li.append(a[i])
    else:
        for j in range(len(li)):
            if li[j] < a[i]:
                li[j] = a[i]
                break

print(len(li))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

colors_tail = [A[0]]
for a in A[1:]:
    for i in range(len(colors_tail)):
        tail = colors_tail[-i-1]
        if tail < a:
            colors_tail.remove(tail)
            bisect.insort(colors_tail, a)
            break
    else:
        bisect.insort(colors_tail, a)

print(len(colors_tail))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from operator import itemgetter, mul
from copy import deepcopy,copy
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n=INT()
    a = [INT() for _ in range(n)]

    lis=[]
    clr=1
    clr_lis=[]


    for i in range(n-1):
        if lis==[]:
            if a[i+1] <= a[i]:
                lis.append(a[i])
                clr+=1

        else:
            if a[i+1] <= a[i]:
                if a[i+1] <= min(lis):
                    lis.append(a[i])
                    clr+=1
                else:
                    lis.sort()
                    lis.pop(0)
                    lis.append(a[i+1])


    
    #print(lis)
    print(clr)

if  __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

colors_tail = [A[0]]
for a in A[1:]:
    for tail in colors_tail[::-1]:
        if tail < a:
            colors_tail.remove(tail)
            bisect.insort(colors_tail, a)
            break
    else:
        bisect.insort(colors_tail, a)

print(len(colors_tail))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())

answer = []
for i in range(n):
    input_num = int(input())
    index = bisect.bisect_left(answer, input_num)
    if index == 0:
        answer.insert(index, input_num)
    else:
        answer[index -1] = input_num
print(len(answer))

Submission status: Time Limit Exceeded

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

for i in range(n):
    if i == 0:
        l.append(a[i])
        continue
    for j in range(len(l)):
        if l[j] < a[i]:
            l[j]=(a[i])
            break
    else:
        l.append(a[i])

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[0]*N
maxA=[-1]*N
cnt=0
for i in range(N):
  A[i]=int(input())
  for k in range(N):
    if maxA[k]<A[i]:
      if maxA[k]==-1:
        cnt+=1
      maxA[k]=A[i]
      break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# ABC134-E

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l1=[I() for _ in range(n)]

  l1.reverse()
  l2=[0]*n

  # c=1

  # # print(l1)
  # for i,x in enumerate(l1):
  #   # print(l2)
  #   if l2[i]==0:
  #     l2[i]=i+1
  #   for j in range(i,n):
  #     y=l1[j]

  #     if c==n-1:
  #       return max(l2)

  #     if x>y and l2[j]==0:
  #       c+=1
  #       l2[j]=i+1
  #       x=y

  # return max(l2)

  l3=[]
  for x in l1:
    l3.append([x])
  # print(l3)
  i=0
  while True:
    if i>=len(l3):
      return len(l3)

    l4=[]
    a=l3[i]
    _a=l3[:i]
    # print(a)
    for j in range(i+1,len(l3)):
      b=l3[j]
      # print(a,b)
      if a[-1]>b[0]:
        a.append(b[0])
      else:
        l4.append(b)

    # print(a,l4)
    l4=_a+[a]+l4
    # print(l4)

    i+=1

    l3=copy.deepcopy(l4)


# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
mi = 10000000000000
res = []
res.append(dat[0])
import bisect
for i in range(1, n):
    a = bisect.bisect_left(res, dat[i])
    if a == 0:
        a = bisect.insort_left(res, dat[i])
    else:
        res[a-1] = dat[i]
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import deque
l = []
for i in range(N):
    l.append(int(input()))
cnt = 0
while len(l) > 0:
    smallest = min(l)
    ind = l.index(smallest)
    small = l.pop(ind)
    memo = []
    for i in range(ind,len(l)):
        if l[i] > small:
            memo.append(l[i])
            small = l[i]
    for i in range(len(memo)):
        l.pop(l.index(memo[i]))
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
temp = []
al = []
for i in range(n):
	l.append(int(input()))

t=0
while(t < len(l)):
	temp.append(l[t])
	# l.pop(0)
	i=t
	while(i<len(l)):
		if temp[-1] < l[i]:
			temp.append(l[i])
			l.pop(i)

		else:
			i += 1
	

	al.append(temp)
	t += 1
	temp=[]

print(len(al))

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

# import random
# print(100000)
# x = [random.randint(1,1000000000) for i in range(100000)]
# for i in x:
#     print(i)
# exit()

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

C = [0] * N
c = 0

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

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 left < N-1:
    if pre == -1:
        left += 1
        pre = A[left]
        right += 1
    elif right >= N:
        # N -= 1
        A[left] = -1
        left += 1
        # A.pop(left)
        l = 1
        ans += 1
        right = left+1
        pre = A[left]
    elif pre < A[right]:
        l += 1
        pre = A[right]
        A[right] = -1
        right += 1
    else:
        right += 1
if pre == -1:
    ans -=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
ans_cond = []
ans_cond.append(A[0])
for i in range(N-1):
	a = A[i+1]
	for j in range(len(ans_cond)):
		if ans_cond[j] < a :
			ans_cond[j] = a
			break
		if j == len(ans_cond)-1:
			ans_cond.append(a)
print(len(ans_cond))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [INT() for _ in range(N)]

# tmp = 0
# ans = 0
# for i in range(1, N):
# 	print(A[i-1], A[i])
# 	if A[i] < A[i-1]:
# 		ans += 1
# print(ans)
# seq = A

ans = 0
LIS = [[A[0]]]
for i in range(1, len(A)):
	for j in range(len(LIS)):
		if A[i] > LIS[j][-1]:
			LIS[j].append(A[i])
			break
	else:
		LIS.append([])
		LIS[-1].append(A[i])
# print(LIS)
print(len(LIS))

Submission status: Time Limit Exceeded

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

ans_l = [a[0]]

for i in range(1,n):
    for j in range(len(ans_l)):
        if a[i] > ans_l[j]:
            ans_l[j] = a[i]
            
            break
    else:
        ans_l.append(a[i])
print(len(ans_l))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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


# N = 2*10**3
# A = [0 for n in range(N)]

# print(A)

visited = [False for n in range(N)]

dp = {}
def search(n,d):
    if n in dp:
        return dp[n]
    maxd = d
    for i in range(n)[::-1]:
        if i in dp:
            maxd = max(dp[i], maxd)
        elif A[i] >= A[n]:
            maxd = max(search(i,d+1), maxd)
    dp[n] = maxd
    return dp[n]

ds = [0 for n in range(N)]
for n in range(N)[::-1]:
    if not n in dp:
        ds[n] = search(n,0)

# print(ds)

print(max(ds)+1)

Submission status: Time Limit Exceeded

Solution code:
#全探索でO(N^2)
N = int(input())
A = [int(input()) for _ in range(N)]

count = 0
tmp = - 10 ** 10
for i in range(N):
    # print ('i', i)
    if A[i] == -10 ** 11:
        continue
    else:
        tmp = A[i]
        count += 1
        for j in range(i + 1, N):
            if tmp < A[j]:
                tmp = A[j]
                A[j] = - 10  ** 11
            if j == N - 1:
                tmp = - 10 ** 10
# print (A)
print (count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def delete_left_maxvals(i,  A_sort_index):
    A_sort_index_left = [k for k in A_sort_index if k < i]
    if len(A_sort_index_left) == 0:
        A_sort_index.remove(i)
        return A_sort_index
    
    max_index = A_sort_index_left[0]
    A_sort_index.remove(i)

    delete_left_maxvals(max_index,  A_sort_index)
    return A_sort_index


def solve(N: int, A: "List[int]"):
    num_colors = 0

    A_sort_index = sorted(range(len(A)), key=lambda k: A[k], reverse=True)
    
    while True:
        max_idx = A_sort_index[0]
        A_sort_index = delete_left_maxvals(max_idx,  A_sort_index)
        
        num_colors += 1
        if len(A_sort_index) == 0:
            break
    print(num_colors)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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



mina = [A[0]]

# print(mina)
# ans = 
for i in range(1,N):
    # print(mina)
    if mina[0]>=A[i]:
        ind = bisect.bisect_left(mina,A[i])
        mina.insert(ind,A[i])
        # ans +=1 
    else:
        ind = bisect.bisect_left(mina,A[i])
        # mina.insert(ind,A[i])
        mina[ind-1]=A[i]
        # if ind == len(mina)-1:
            
        #     del(mina[-2])
        # else:
        #     # print("a")
        #     del(mina[ind-1])


# print(mina)
    
print(len(mina))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())

answer = []
for i in range(n):
    input_num = int(input())
    list_num = len(answer)
    index = bisect.bisect_left(answer, input_num)
    if index == 0:
        answer.insert(index, input_num)
    else:
        answer[index -1] = input_num
print(len(answer))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(input()) for i in range(N)]
a_small = a[0]
a_small_list = [a_small]
color_count = 1
for i in a[1:]:
    if i <= min(a_small_list):
        color_count += 1
        a_small_list.append(i)
    else:
        a_small_able = [j for j in a_small_list if j < i]
        a_small_list.remove(max(a_small_able))
        a_small_list.append(i)
print(color_count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
mi = 10000000000000
res = []
res.append(dat[0])
import bisect
for i in range(1, n):
    a = bisect.bisect_left(res, dat[i])
    if a == 0:
        res = [dat[i]] + res
    else:
        res[a-1] = dat[i]
    #print(res)
print(len(res))

Submission status: Time Limit Exceeded

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

dp = [ [0, -1, -1] for i in range(n + 1) ] ## [length, sequence_top_num, sequence_second_num]

ans = 0
while sum( x==-2 for x in num_list) < n:
    longest_list = []
    for i in range(n):
        if dp[i][1] >= num_list[i]:
            if dp[i][2] < num_list[i]:
                longest_list.pop()
                longest_list.append(i)
                dp[i+1][0] = dp[i][0]
                dp[i+1][1] = num_list[i]
                dp[i+1][2] = dp[i][2]
            else:
                dp[i+1][0] = dp[i][0]
                dp[i+1][1] = dp[i][1]
                dp[i+1][2] = dp[i][2]
        else:
            dp[i+1][0] = dp[i][0] + 1
            dp[i+1][2] = dp[i][1]
            dp[i+1][1] = num_list[i]
            longest_list.append(i)
    
    for indx in longest_list:
        num_list[indx] = -2
    
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 0
l = [int(input())]
for _ in range(N-1):
    k = int(input())
    while(1):
        if k <= l[c]:
            c += 1
        else:
            l[c] = k
            break
        if c == len(l):
            l.append(k)
            c = 0
            break
    
print(len(l))

Submission status: Time Limit Exceeded

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

_max = 10**9+1
ans = [[_max]]

for i in range(n):
    frg = 0
    for j in range(len(ans)):
        _max = ans[j][-1]
        if a[n-1-i] < _max:
            ans[j].append(a[n-1-i])
            frg = 1
            break
    if frg==0:
        ans += [[a[n-1-i]]]

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
 
 
def solve(N: int, A: "List[int]"):
 
    a = [-INF]
 
    def isOK(index, key):
        return a[index] < key
 
    def binary_search(key):
        ng = -1
        ok = len(a)
 
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok
 
    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return
 
 
def main():
 
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
c = 0
while len(a) > 0:
    c_max = 1000000001
    for i in range(len(a) - 1, -1, -1):
        if a[i] < c_max:
            c_max = a[i]
            a.pop(i)
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = int(input())
A = [a]
C = [a]

for _ in range(N-1):
    a = (int(input()))
    for i, c in enumerate(C):
        if c < a:
            C[i] = a
            break
    else:
        C.append(a)
print(len(C))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np

n = int(input())
for i in range(n):
    a = int(input())
    if i == 0:
        ans = np.array([a])
        continue
    else:
        if ans[len(ans)-1] < a:
            ans[len(ans)-1] = a
        elif ans[0] >= a:
            ans = np.append(ans,a)
        else:
            index_a = np.where(ans==a)[0]
            if len(index_a)==0:
                for j in reversed(range(len(ans))):
                    if a > ans[j]:
                        ans[j] = a
                        break
            else:
                ans[index_a[0]] = a
        ans = np.sort(ans)
        #print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

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


mm = max(A)+2
B=[0 for i in range(mm)]
for i in range(n):
    if A[i]<=mm:
        B[A[i]]+=1
        mm=A[i]
    else:
        t=A[i]
        while B[t]==0:
            t-=1
        B[t]-=1
        B[A[i]]+=1
        #print(B)
        if mm==t and B[t]==0:
            while B[mm]==0:
                mm+=1
print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
a = [int(input())]
inp = 0
min_num = 0
ctr = 1

for i in range(1, N):
    inp = int(input())
    a2 = [j for j in a if j < inp]
    if a2 != []:
        max_num = max(a2)
        a[a.index(max_num)] = inp
    else:
        a.append(inp)
        ctr += 1
print(ctr)

Submission status: Time Limit Exceeded

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

ans = [l[0]]
for i in range(1, len(l)):
    if l[i] <= ans[-1]:
        ans.append(l[i])
        continue
    for j in range(len(ans)):
        if l[i] > ans[j]:
            ans[j] = l[i]
            break
    list.sort(ans, reverse=True)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = []
colored_nums = []

for i in range(N):
    num = int(input())
    nums.append(num)
    if(i==0):
        colored_nums.append(num)
    else:
        sa = 0
        index = -1
        for j in range(len(colored_nums)):
            if(num>colored_nums[j]):
                if(num-colored_nums[j]>sa):
                    sa = num-colored_nums[j]
                    index = j
        if(index==-1):
            colored_nums.append(num)
        else:
            colored_nums[j] = num

print(len(colored_nums))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def sol():
    n=int(input())
    new=[int(input()) for _ in [0]*n]
    a=[new[0]]
    for i in range(1,n):
        if a[-1]>=new[i]:a.append(new[i])
        else:
            for j in range(len(a)):
                if a[j]<new[i]:a[j]=new[i];break
    print(len(a))
sol()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())

lasts=deque([int(input())])
for _ in range(N-1):
    a=int(input())
    
    if a<=lasts[0]:
        lasts.appendleft(a)
    else:
        for i in range(len(lasts)-1, -1, -1):
            if lasts[i]<a:
                lasts[i]=a
                break

print(len(lasts))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n=INT()
    a = [INT() for _ in range(n)]

    lis=[]
    clr=1
    clr_lis=[]


    for i in range(n-1):
        if lis==[]:
            if a[i+1] <= a[i]:
                lis.append(a[i])
                clr+=1

        else:
            if a[i+1] <= a[i]:
                if a[i+1] <= min(lis):
                    lis.append(a[i])
                    clr+=1
                else:
                    lis.remove(min(lis))
                    lis.append(a[i+1])


    
    #print(lis)
    print(clr)

if  __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
data = []

for _  in range(N):
    data.append(int(input()))

count = 0
while data != []:
    tmp = -1

    for d in data[:]:

        if d > tmp:
            tmp = d
            data.remove(d)

    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = [int(input()) for _ in range(n)]
ans=0
for i in range(n-1):
  if min(a[i+1:])>=a[i]:
    ans+=1
print(ans+1)

Submission status: Time Limit Exceeded

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

ans = [a[0]]
count = 0
for i in range(1,n):
  #  print(a[i],ans[count],count)
    if a[i] > ans[count]:
        ans[count] = a[i]
    else:
        mi = min(ans)
   #     print(mi,ans.index(mi))
        if mi < a[i]:
            idx = ans.index(mi)
            ans[idx] = a[i]
            count = idx
        else:
            ans.append(a[i])
            count += 1
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [int(input()) for _ in range(n)]

c = 0

for i in range(n):
#  print('i', i)
  if s[i] >= 0:
    c += 1
#    print('ic', i)
    a = s[i]
    
    for j in range(i, len(s)):
      if s[j] > a:
        a = s[j]
        s[j] = -1
#        print('j', j,a)

print (c)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.misc import comb
sys.setrecursionlimit(1000000)
 
n = int(input())

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

color = [[-1] for i in range(n+1)]

max_j = 0
for i in range(n):
    for j in range(n):
        #print(color[j][-1])
        if a[i] > color[j][-1]:
            color[j].append(a[i])
            max_j = max(max_j,j+1)
            break
            
print(max_j)

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
 
N = int(input())
 
lis = []
 
A1 = int(input())
 
 
lis.append(A1)
 
 
for i in range(N-1):
 
    A = int(input())
 
    flag = True
    ins = bisect.bisect_left(lis,A)
 
    if ins == 0:
        lis.insert(0,A)
 
    if lis[ins-1] < A:
        lis[ins-1] = A
 
"""
    for l in lis:
 
 
 
        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break
 
    if flag:
        lis.append(A)
"""
 
#print (lis)
print (len(lis))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
l = [a[n - 1]]

for i in range(n - 1)[::-1]:
    tmp = a[i]
    if tmp >= l[-1]:
        l.append(tmp)
    else:
        for j in range(len(l)):
            if tmp < l[j]:
                l[j] = tmp
                break

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = []
ans = []

for i in range(N):
    li.append(int(input()))

ans.append(li[0])

for i in range(1, N):
    ans.sort(reverse=True)
    if li[i] <= min(ans):
        ans.append(li[i])
    else:
        for j in range(len(ans)):
            if ans[j] < li[i]:
                ans[j] = li[i]
                break

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N=list(map(int, input().split()))
N=N[0]
A=[]
for i in range(N):
    A.append(int(input()))
color=0
while len(A)>0:
    color+=1
    max=-1
    sub=[]
    for i in A:
        if i>max:
            max=i
        else:
            sub.append(i)
    A=sub
    
print(color)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
al=[int(input()) for _ in range(n)]
ans=[]
for a in al:
    for i in range(len(ans)):
        if max(ans[i])<a:
            ans[i].append(a)
            break
    else:
        ans.append([a])
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import *

def f(n):
    r = []
    for _ in range(n):
        a = int(input())
        if not r:
            r.append(a)
            continue
        i = bisect_left(r, a)
        if i:
            r.insert(i, a)
            del r[i - 1]
        else:
            r = [a] + r
    print(len(r))

n = int(input())
f(n)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a_list = []
for i in range(N):
    a_list.append(int(input()))
color_counter = 0
for i in range(N):
    color_counter += 1
    compare_a = a_list.pop(0)
    next_a_list = []
    for ite in a_list:
        if compare_a < ite:
            compare_a = ite
        else:
            next_a_list.append(ite)
    if len(next_a_list) == 0:
        break
    else:
        a_list = next_a_list
print(color_counter)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

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

ans = 0
q = [A[0]]
p = A[0]
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if p >= A[i] and insert_index == 0:
        q.insert(0, A[i])
        ans += 1
    else:
        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 _ in range(N)]

C = [[A[0]]]
head = [A[0]]
for i in range(N-1):
    nex = A[i+1]
    for j in range(len(head)):
        if nex > head[j]:
            # C[j].append(A[i+1])
            head[j] = nex
            break
    else:        
        C.append([nex])  # new color
        head.append(nex)

print(len(C))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

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

c = []
c.append(a[0])
for ai in a[1:]:
    ci = bisect_right(c, ai)
    if ci == 0 or c[ci - 1] == ai:
        c.append(ai)
        c.sort()
    else:
        c[ci - 1] = ai
        c.sort()

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = [A[0]]

for a in A[1:]:
    if a <= ans[0]:  # 色を増やすしかない
        ans.insert(0, a)
    else:  # 既存の色のどこかに追加
        idx = bisect.bisect_left(ans, a)
        ans[idx-1] = a

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a = []
for x in range(0, N):
  a.append(int(input()))

ans = 0
while (len(a) > 0):
  if (a.index(min(a)) < a.index(max(a))):
    a = a[:a.index(min(a))] + a[a.index(max(a)) + 1:]
  else:
    a = a[:a.index(min(a)) + a.index(max(a))] + a[a.index(min(a)) + a.index(max(a)) + 1:]
  ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#全探索でO(N^2)
N = int(input())
A = [int(input()) for _ in range(N)]

count = 0
tmp = - 10 ** 10
for i in range(N):
    # print ('i', i)
    if A[i] == -10 ** 11:
        continue
    if tmp == -10 ** 10:
        tmp = A[i]
        count += 1
        for j in range(i + 1, N):
            if tmp < A[j]:
                tmp = A[j]
                A[j] = - 10  ** 11
            if j == N - 1:
                tmp = - 10 ** 10
# print (A)
print (count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a_list = []
for i in range(N):
    a_list.append(int(input()))
color_counter = 0
for i in range(N):
    color_counter += 1
    compare_a = a_list.pop(0)
    next_a_list = []
    for idx, ite in enumerate(a_list[:]):
        if compare_a < ite:
            compare_a = ite
        else:
            next_a_list.append(ite)
    if len(next_a_list) == 0:
        break
    else:
        a_list = next_a_list
print(color_counter)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

inf = float('inf')

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

seen = [False] * n
cnt = 0

flg = True
while flg:
    flg = False
    num = -1
    for i, aa in enumerate(a):
        if seen[i]:
            continue
        flg = True
        if num == -1:
            num = aa
            seen[i] = True
            cnt += 1
        else:
            if aa > num:
                num = aa
                seen[i] = True

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
m=[-1]

for i in range(N):
    A=int(input())
    if A<=m[0]:
        m.insert(0,A)
    else:
        for j in range(len(m)-1,-1,-1):
            if m[j]<A:
                m[j]=A
                break

print(len(m))