Problem:


Score : 600 points

Problem Statement

We have one slime.

You can set the health of this slime to any integer value of your choice.

A slime reproduces every second by spawning another slime that has strictly less health. You can freely choose the health of each new slime. The first reproduction of our slime will happen in one second.

Determine if it is possible to set the healths of our first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals a multiset S.

Here S is a multiset containing 2^N (possibly duplicated) integers: S_1,~S_2,~...,~S_{2^N}.

Constraints

All values in input are integers.

1 \leq N \leq 18

1 \leq S_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 ... S_{2^N}

Output

If it is possible to set the healths of the first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals S, print Yes; otherwise, print No.

Sample Input 1

2
4 2 3 1

Sample Output 1

Yes

We will show one way to make the multiset of the healths of the slimes that will exist in 2 seconds equal to S.

First, set the health of the first slime to 4.

By letting the first slime spawn a slime whose health is 3, the healths of the slimes that exist in 1 second can be 4,~3.

Then, by letting the first slime spawn a slime whose health is 2, and letting the second slime spawn a slime whose health is 1, the healths of the slimes that exist in 2 seconds can be 4,~3,~2,~1, which is equal to S as multisets.

Sample Input 2

2
1 2 3 1

Sample Output 2

Yes

S may contain multiple instances of the same integer.

Sample Input 3

1
1 1

Sample Output 3

No

Sample Input 4

5
4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3

Sample Output 4

No



Sample input:
2
4 2 3 1


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    hq = [1]
    num = [0]*(2**(n+1)+1)
    num[0] = 10**10
    nqi = []
    for i in s:
#        print(hq)
        while hq:
            qi = hpq.heappop(hq)
            if num[qi//2] == i:
                if not hq:
                    print("No")
                    exit()
                nqi.append(qi)
                continue
            ndi = qi*(2**(n-len(str(format(qi,"b")))+1))
            while ndi > qi:
                num[ndi] = i
                hpq.heappush(hq,(ndi//2)*2+1)
                ndi //= 2
            num[qi] = i
            while nqi:
                j = nqi.pop()
                hpq.heappush(hq,j)
            break
    print("Yes")



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    hq = [1]
    num = [0]*(2**(n+1)+1)
    num[0] = 10**10
    nqi = []
    for i in s:
#        print(hq)
        while hq:
            qi = hpq.heappop(hq)
            if num[qi//2] == i:
                if not hq:
                    print("No")
                    exit()
                nqi.append(qi)
                continue
            ndi = qi*(2**(n-len(str(format(qi,"b")))+1))
            while ndi > qi:
                num[ndi] = i
                hpq.heappush(hq,(ndi//2)*2+1)
                ndi //= 2
            num[qi] = i
            for j in nqi:
                hpq.heappush(hq,j)
            nqi = []
            break
    print("Yes")



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
if len(a) == 2 ** n:
  print('Yes')
  exit(0)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
  n = int(input())
  a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
  g = [0]*(n+1)
  g[n] = 1
  for _, x in a:
    if sum(g) < x:
      print('No')
      break
    t = [0]*(n+1)
    for i in range(n, -1, -1):
      if g[i] <= x:
        t[i-1] = t[i] + g[i]
        x -= g[i]
        g[i] = 0
      else:
        t[i-1] = t[i] + x
        g[i] -= x
        x = 0
      t[i] += g[i]
    t[n] = 0
    g = t
  else:
    print('Yes')
  return

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
N2 = 2**N
S = list(map(int, input().split()))
S = [-s for s in S]
heapq.heapify(S)

slimes = [heapq.heappop(S)]
num = 1
for i in range(N):
  slimes.sort(reverse=True)
  n = num
  temp = []
  while n and S:
    s = heapq.heappop(S)
    if s > slimes[n-1]:
      slimes.append(s)
      n -= 1
    else:
      temp.append(s)
  
  if n:
    print('No')
    quit()
  
  num *= 2
  for t in temp:
    heapq.heappush(S, t)


print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from copy import deepcopy

n = int(input())
s = list(map(int, input().split()))

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_prev = deepcopy(made)
    tmp = []

    while made_prev:
        made_val = heappop(made_prev)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made, left_val)

    for e in tmp:
        heappush(left, e)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from copy import deepcopy

n = int(input())
s = list(map(int, input().split()))

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_nxt = deepcopy(made)
    tmp = []

    while made:
        made_val = heappop(made)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made_nxt, left_val)

    made = made_nxt

    for e in tmp:
        heappush(left, e)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
s = list(map(int, input().split()))

first = max(s)
made = [first]
s.remove(first)
s.append(0)
s.sort()

for _ in range(n):
    made_now = []
    for e in made:
        i = bisect_left(s, e)
        make = s.pop(i - 1)
        if make == 0:
            print("No")
            exit()
        made_now.append(make)

    made += made_now

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
S = list(map(int,input().split()))
count = Counter(S)
S = sorted(S)
T = sorted(list(set(S)))
M = len(T)
pre = {T[i]:T[i-1] if i > 0 else 0 for i in range(M)}

l = [S[-1]]
count[S[-1]] -= 1

while len(l) < 2**N:
    for n in l[:]:
        m = pre[n]
        if m == 0:
            print('No')
            exit()
        while count[m] == 0:
            pre[n] = pre[m]
            m = pre[n]
            if m == 0:
                print('No')
                exit()
        l.append(m)
        count[m] -= 1

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, *S = map(int, open(0).read().split())

    S.sort(reverse=True)

    P = [S[0]]
    S[0] = INF
    for _ in range(N):
        Q = P[:]
        while Q:
            q = heappop(Q)

            for i, s in enumerate(S):
                if s < q:
                    heappush(P, s)
                    S[i] = INF
                    break
            else:
                print("No")
                quit()

    print("Yes")


main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, *S = map(int, open(0).read().split())

    S.sort(reverse=True)

    P = [S[0]]
    for _ in range(N):
        Q = P[:]
        while Q:
            q = heappop(Q)

            for i, s in enumerate(S):
                if s < q:
                    heappush(P, s)
                    S[i] = INF
                    break
            else:
                print("No")
                quit()

    print("Yes")


main()

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")

N, *S = map(int, open(0).read().split())

S.sort(reverse=True)

T = [S[0]]
for _ in range(N):
    T.sort()

    Q = T[:]
    while Q:
        q = Q.pop()

        for i, s in enumerate(S):
            if s < q:
                T.append(s)
                S[i] = INF
                break
        else:
            print("No")
            quit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

INF = float("inf")

N, *S = map(int, open(0).read().split())

S.sort(reverse=True)

P = [S[0]]
for _ in range(N):
    Q = P[:]
    while Q:
        q = heappop(Q)

        for i, s in enumerate(S):
            if s < q:
                heappush(P, s)
                S[i] = INF
                break
        else:
            print("No")
            quit()

print("Yes")

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = LI()
h = []
for i in s:
    heappush(h,-i)
x = heappop(h)
use = [-x]
for _ in range(n):
    use_tmp = []
    for i in use:
        rest_tmp = []
        while h:
            x = heappop(h)
            x = -x
            if i > x:
                use_tmp.append(x)
                break
            else:
                rest_tmp.append(x)
        for j in rest_tmp:
            heappush(h,-j)
    use += use_tmp
if len(use) == 2**n:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = LI()

h = []
for i in range(2**n):
    heappush(h,-s[i])
x = heappop(h)
use = [-x]
for i in range(n):
    tmp2 = []
    for j in use:
        tmp = []
        while h:
            x = heappop(h)
            x = -x
            if j > x:
                tmp2.append(x)
                break
            else:
                tmp.append(x)
        else:
            print('No')
            quit()
        for k in tmp:
            heappush(h,-k)
    use += tmp2
print('Yes')

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = LI()

h = []
for i in range(2**n):
    heappush(h,-s[i])
x = heappop(h)
use = [-x]
for i in range(n):
    tmp2 = []
    for j in use:
        tmp = []
        while h:
            x = heappop(h)
            x = -x
            if j > x:
                tmp2.append(x)
                break
            else:
                tmp.append(x)
        else:
            print('No')
            quit()
        for k in tmp:
            heappush(h,-k)
    for j in tmp2:
        use.append(j)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n**3)
    return

#B
def B():
    n = II()
    a = LI()
    b = LI()
    c = LI()
    ans = 0
    for i in range(n):
        ans += b[a[i] - 1] + (c[a[i] - 1] if i != n - 1 and a[i] + 1 == a[i + 1] else 0)
    print(ans)
    return

#C
def C():
    n = II()
    b = LI()
    ans = b[0]
    for i in range(n-2):
        if b[i] >= b[i + 1]:
            ans += b[i + 1]
        else:
            ans += b[i]
    print(ans+b[-1])
    return

#D
def D():
    n, k = LI()
    s = S()
    a = []
    for i in range(n):
        if i == n - 1:
            a.append(s[i])
        elif s[i] != s[i + 1]:
            a.append(s[i])
    print(min(n - 1, n - len(a) + 2 * k))
    return

# E
# 解説AC
# Piが何個使えるかというとこまでは良くて
# そのPiよりも大きい数字が左に2個右に2個必要というところまではいけた
# 問題の本質を解決できてはいない
# ここから解説
# 大きい順からみて見たものに対してインデックスを保持
# ここからbisectを使えばlogNでi付近のすでに追加したインデックスを持ってこれる
# あと少しだけどその少しが遠い
# ↑
# これは嘘
# BITを使え
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i
        while x < self.size:
            self.bit[x] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i
        while x > 0:
            res += self.bit[x]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        ok = self.size
        ng = 0
        while abs(ok - ng) != 1:
            mid = (ok + ng)//2
            if self.sum(mid) >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def __len__(self):
        return self.size

def E():
    n = II()
    a = LI()
    dic = defaultdict(int)
    for i, ai in enumerate(a):
        dic[ai] = i+1
    bit = BinaryIndexedTree(n+1)
    num = [i + 1 for i in range(n)][::-1]
    ans = 0
    for i in num:
        c = dic[i]
        L = bit.sum(c)
        bit.add(c,1)
        R = n-i-L 
        a = bit.search(L-1) if L >= 2 else 0
        b = bit.search(L) if L >= 1 else 0
        d = bit.search(L+2) if R >= 1 else n+1
        e = bit.search(L+3) if R >= 2 else n+1
        tmp = 0
        if b != 0:
            tmp += (b-a) * (d-c)
        if d != 0:
            tmp += (e-d) * (c-b)
        ans += i * tmp

    print(ans)
    return

#F
def F():
    n = II()
    s = LI()
    s.sort(reverse=True)
    x = list(sorted(set(s)))[::-1]
    d = defaultdict(int)
    di = defaultdict(int)
    for i, xi in enumerate(x):
        d[xi] = i
        di[xi] = i + 1
    ma = i + 1
    num = [0] * (ma)
    for si in s:
        num[d[si]] += 1
    l = [s[0]]
    num[0] -= 1
    for i in range(n):
        tmp = l[::1]
        for li in l:
            if di[li] < ma and num[di[li]]:
                num[di[li]] -= 1
                tmp.append(x[di[li]])
            else:
                while di[li] < ma and (not num[di[li]]):
                    di[li] += 1
                if di[li] >= ma:
                    print("No")
                    return
                tmp.append(x[di[li]])
                num[di[li]] -= 1
        l = tmp[::1]
    print("Yes")
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n**3)
    return

#B
def B():
    n = II()
    a = LI()
    b = LI()
    c = LI()
    ans = 0
    for i in range(n):
        ans += b[a[i] - 1] + (c[a[i] - 1] if i != n - 1 and a[i] + 1 == a[i + 1] else 0)
    print(ans)
    return

#C
def C():
    n = II()
    b = LI()
    ans = b[0]
    for i in range(n-2):
        if b[i] >= b[i + 1]:
            ans += b[i + 1]
        else:
            ans += b[i]
    print(ans+b[-1])
    return

#D
def D():
    n, k = LI()
    s = S()
    a = []
    for i in range(n):
        if i == n - 1:
            a.append(s[i])
        elif s[i] != s[i + 1]:
            a.append(s[i])
    print(min(n - 1, n - len(a) + 2 * k))
    return

# E
# 解説AC
# Piが何個使えるかというとこまでは良くて
# そのPiよりも大きい数字が左に2個右に2個必要というところまではいけた
# 問題の本質を解決できてはいない
# ここから解説
# 大きい順からみて見たものに対してインデックスを保持
# ここからbisectを使えばlogNでi付近のすでに追加したインデックスを持ってこれる
# あと少しだけどその少しが遠い
# ↑
# これは嘘
# BITを使え
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i
        while x < self.size:
            self.bit[x] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i
        while x > 0:
            res += self.bit[x]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        ok = self.size
        ng = 0
        while abs(ok - ng) != 1:
            mid = (ok + ng)//2
            if self.sum(mid) >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def __len__(self):
        return self.size

def E():
    n = II()
    a = LI()
    dic = defaultdict(int)
    for i, ai in enumerate(a):
        dic[ai] = i+1
    bit = BinaryIndexedTree(n+1)
    num = [i + 1 for i in range(n)][::-1]
    ans = 0
    for i in num:
        c = dic[i]
        L = bit.sum(c)
        bit.add(c,1)
        R = n-i-L 
        a = bit.search(L-1) if L >= 2 else 0
        b = bit.search(L) if L >= 1 else 0
        d = bit.search(L+2) if R >= 1 else n+1
        e = bit.search(L+3) if R >= 2 else n+1
        tmp = 0
        if b != 0:
            tmp += (b-a) * (d-c)
        if d != 0:
            tmp += (e-d) * (c-b)
        ans += i * tmp

    print(ans)
    return

#F
def F():
    n = II()
    s = LI()
    s.sort(reverse=True)
    x = list(sorted(set(s)))[::-1]
    d = defaultdict(int)
    di = defaultdict(int)
    for i, xi in enumerate(x):
        d[xi] = i
        di[xi] = i + 1
    ma = i + 1
    num = [0] * (ma)
    for si in s:
        num[d[si]] += 1
    l = [s[0]]
    num[0] -= 1
    for i in range(n):
        tmp = l[::1]

        for li in l:
            if di[li] < ma and num[di[li]]:
                num[di[li]] -= 1
                tmp.append(x[di[li]])
            else:
                while di[li] < ma and (not num[di[li]]):
                    di[li] += 1
                if di[li] >= ma:
                    print("No")
                    return
                tmp.append(x[di[li]])
                num[di[li]] -= 1
        l = list(sorted(tmp[::1]))
    print("Yes")
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Time Limit Exceeded

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

S.sort(reverse = True)
L = []

cnt = 1
for i in range(1, len(S)):
  if S[i] == S[i - 1]:
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
L.append(cnt)

if L[0] != 1:
  print("No")
  exit()

DP = [[0] * N for _ in range(len(L))]
S = [0] * len(L)

for i in range(N):
  DP[0][i]= 1

for i in range(1, len(L)):
  for j in range(N):
    DP[i][j] = DP[i - 1][j]
  
  t = L[i]
  k = 0
  P = [0] * N
  for j in range(N):
    P[j] = k
    if DP[i][j] > t:
      DP[i][j] -= t
      k += t
      t = 0
    else:
      t -= DP[i][j]
      k += DP[i][j]
      DP[i][j] = 0
  if t != 0:
    print("No")
    exit()
  for j in range(N):
    DP[i][j] += P[j]

print("Yes")

Submission status: Time Limit Exceeded

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

S.sort()

parents = [S.pop()]

for _ in range(N):
    parents.sort(reverse=True)
    for i in parents[:]:
        not_use = []

        while S:
            tmp = S.pop()
            if tmp < i:
                parents.append(tmp)
                break
            else:
                not_use.append(tmp)
        else:
            print('No')
            exit()

        S.extend(not_use[::-1])
else:
    print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
n=int(input())
S = list(map(int,input().split()))

S.sort(reverse=True)
S = deque(S)
S.append(0)
#print(S)
ans = deque([S[0]])
S.popleft()
tmp = deque([])

for i in range(n):
  for j in ans:
    #parent = j
    for k in S:
      #child = k
      if k == 0:
        print('No')
        sys.exit()
      elif k < j:
        S.remove(k)
        tmp.append(k)
        break
  for j in tmp:
    ans.append(j)
  tmp = []
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys

def bsearch(target, min_i, max_i, func):
    # func(index) < target <= func(index+1) となるindexを返す
    if func(max_i) < target:
        return max_i
    if target <= func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) < target:
            if target <= func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

n=int(input())
xs = sorted(list(map(int,input().split())))
bs = [xs.pop()]
cs = xs
for _ in range(n):
    for bi in range(len(bs)):
        ci = bsearch(bs[bi], 0, len(cs)-1, lambda x : cs[x])
        if ci == None:
            print("No")
            sys.exit()
        bs.append(cs[ci])
        del cs[ci]
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys

def bsearch(target, min_i, max_i, func):
    # func(index) < target <= func(index+1) となるindexを返す
    if func(max_i) < target:
        return max_i
    if target <= func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) < target:
            if target <= func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

def bb(bs, cs):
    for bi in range(len(bs)):
        ci = bsearch(bs[bi], 0, len(cs)-1, lambda x : cs[x])
        if ci == None:
            print("No")
            sys.exit()
        bs.append(cs[ci])
        del cs[ci]
    return bs, cs

def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    while True:
      if bs[bi] > cs[ci]:
        bi += 1
        bs.append(cs[ci])
        del cs[ci]
      else:
        ci += 1
      if bi == bl or ci == len(cs):
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, cs

n=int(input())
xs = sorted(list(map(int,input().split())))
bs = [xs.pop()]
cs = xs
for _ in range(n):
    x = bb(bs, cs)
    if x:
        bs, cs = x
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    while True:
      if bs[bi] > cs[ci]:
        bi += 1
        bs.append(cs[ci])
        del cs[ci]
      else:
        ci += 1
      if bi == bl or ci == len(cs):
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, cs

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], cs)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    while True:
      if bs[bi] > cs[ci]:
        bi += 1
        bs.append(cs[ci])
        del cs[ci]
      else:
        ci += 1
      if bi == bl or ci == len(cs):
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, cs

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], sorted(cs)[::-1])

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl = len(bs)
    for bi in range(bl):
      for i, c in enumerate(cs):
        if bs[bi] > c:
            bs.append(c)
            del cs[i]
            break
      else:
        print("No")
        sys.exit()
    return bs, cs
n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(bs, cs)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    nbs = []
    for b in bs:
      for i, c in enumerate(cs):
        if b > c:
            nbs.append(c)
            del cs[i]
            break
      else:
        print("No")
        sys.exit()
    return bs+nbs, cs
n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(bs, cs)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
n = int(input())
children = sorted([int(s) for s in input().split()],reverse=True)
parents = [children.pop(0)]
generable = True
for generation in range(n):
    parents.sort()
    numparents=1<<generation
    for i in range(numparents):
        parent=parents[i]
        birth=False
        numchildren = len(children)
        for j in range(numchildren):
            child=children[j]
            if child<parent:
                children.pop(j)
                birth=True
                parents.append(child)
                break
        generable &= birth
        if not generable:
            break
    if not generable:
        break
print('Yes' if generable else 'No')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
n=int(input())
S = list(map(int,input().split()))

S.sort(reverse=True)
S = deque(S)
S.append(0)
#print(S)
ans = deque([S[0]])
S.popleft()
tmp = deque([])

for i in range(n):
  for j in ans:
    #parent = j
    for k in S:
      #child = k
      if k == 0:
        print('No')
        sys.exit()
      elif k < j:
        S.remove(k)
        tmp.append(k)
        break
  for j in tmp:
    ans.append(j)
  tmp = []
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
n=int(input())
S = list(map(int,input().split()))

S.sort(reverse=True)
S = deque(S)
S.append(0)
#print(S)
ans = [S[0]]
S.popleft()
tmp = []

for i in range(n):
  for j in ans:
    #parent = j
    for k in S:
      #child = k
      if k == 0:
        print('No')
        sys.exit()
      elif k < j:
        S.remove(k)
        tmp.append(k)
        break
  for j in tmp:
    ans.append(j)
  tmp = []
ans.sort(reverse=True)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)
n=i1()
s=i2()
m=10**9+1
import heapq
import bisect
s.sort()
x=[s[-1]]
s[-1]=m
a="Yes"
for i in range(n):
 y=[]
 for j in range(1<<i):
   s.sort()
   z=bisect.bisect_left(s,x[j])-1
   if z<0:
     a="No"
   y.append(s[z])
   s[z]=m
 x+=y
 x.sort(reverse=True)
print(a)