Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

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

Sample Output 4

5

Sample Input 5

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

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
cd.sort(reverse=True)

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[i].append(j)

ans = []
temp= [[0, {-1}]]

while temp:
    q = temp.pop()
    if q[0] == N:
        ans.append(len(q[1])-1)
    else:
        for i in g[q[0]]:
            if not i in q[1]:
                s = q[1] | {i}
                temp.append([q[0]+1, s])
        temp.append([q[0]+1, q[1]])            
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
cd.sort(reverse=True)

g = [[] for _ in range(N)]

for i, pab in enumerate(ab):
    for j, pcd in enumerate(cd):
        if pab[0] < pcd[0] and pab[1] < pcd[1]:
            g[i].append(j)

ans = []
temp= [[0, {-1}]]

while temp:
    q = temp.pop()
    if q[0] == N:
        ans.append(len(q[1])-1)
    else:
        for i in g[q[0]]:
            if not i in q[1]:
                s = q[1] | {i}
            else: s = q[1]
            temp.append([q[0]+1, s])
        temp.append([q[0]+1, q[1]])            
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
red_point_list = [[int(j) for j in input().split()] for i in range(n)]
blue_point_list = [[int(j) for j in input().split()] for i in range(n)]

px = red_point_list[0][0]
py = red_point_list[0][1]

tmp = []
for i, p in enumerate(blue_point_list):
    if px < p[0] and py < p[1]:
        new_blue_points = blue_point_list.copy()
        new_blue_points.pop(i)
        tmp.append((1, new_blue_points))

if len(tmp) == 0:
    tmp = [(0, blue_point_list)]

for a, b in red_point_list[1:]:
    new_tmp = []
    for count, blue_points in tmp:
        for i, p in enumerate(blue_points):
            if a < p[0] and b < p[1]:
                new_blue_points = blue_points.copy()
                new_blue_points.pop(i)
                new_tmp.append((count+1, new_blue_points))
            else:
                new_tmp.append((count, blue_points))
    tmp = new_tmp

print(max(tmp, key=lambda x: x[0])[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
red_point_list = [[int(j) for j in input().split()] for i in range(n)]
blue_point_list = [[int(j) for j in input().split()] for i in range(n)]

count = 0
memo = []

def func(red_points, blue_points, count):
    
    if len(red_points) == 0:
        memo.append(count)
    else:
        a = red_points[0][0]
        b = red_points[0][1]
        x = 0
        for i, p in enumerate(blue_points):
            if a < p[0] and b < p[1]:
                new_red_points = red_points[1:]
                new_blue_points = blue_points.copy()
                new_blue_points.pop(i)
                new_count = count + 1
                x += 1
                func(new_red_points, new_blue_points, new_count)
        if x == 0:
            new_red_points = red_points[1:]
            new_blue_points = blue_points.copy()
            func(new_red_points, new_blue_points, count)


func(red_point_list, blue_point_list, count)
print(max(memo))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
r=[list(map(int, input().split())) for i in range(n)]
b=[list(map(int, input().split())) for i in range(n)]
p=[]
v=[0]*n

def dfs(li,m,num):
    global ma

    if num==n:
        ma=max(ma,m)
        return

    for i in p[num]:
        if li[i]==0:
            li[i]=1
            m+=1
            dfs(li,m,num+1)
            li[i]=0
            m-=1
    dfs(li,m,num+1)

ma = 0

for i in range(n):
    q=[]
    for j in range(n):
        if r[i][0]<b[j][0] and r[i][1]<b[j][1]:
            q.append(j)
    p.append(q)

dfs(v,0,0)

print(ma)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
AB=list()
for i in range(N):
    AB.append(list(map(int,input().split())))
CD=list()
for i in range(N):
    CD.append(list(map(int,input().split())))
import itertools
ans=0
for v in itertools.permutations(CD):
    s=0
    for x,y in zip(AB,v):
        if x[0]<y[0] and x[1]<y[1]:
            s+=1
    if s>ans:
        ans=s
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    Reds = [list(map(int, input().split(" "))) for i in range(N)]
    Blues = [list(map(int, input().split(" "))) for i in range(N)]
    maxpairs = 0
    for blues in itertools.permutations(Blues, N):
        npairs = 0
        for i in range(N):
            if able_to_be_pair(Reds[i], blues[i]):
                npairs += 1
        maxpairs = max(maxpairs, npairs)
    print(maxpairs)

def able_to_be_pair(red, blue):
    return True if (blue[0] - red[0]) > 0 and (blue[1] - red[1]) > 0 else False

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    Reds = [list(map(int, input().split(" "))) for i in range(N)]
    Blues = [list(map(int, input().split(" "))) for i in range(N)]
    maxpairs = 0
    BluePerms = permutations(Blues)
    for blues in BluePerms:
        npairs = 0
        for i in range(N):
            if able_to_be_pair(Reds[i], blues[i]):
                npairs += 1
        maxpairs = max(maxpairs, npairs)
    print(maxpairs)

def able_to_be_pair(red, blue):
    return True if (blue[0] - red[0]) > 0 and (blue[1] - red[1]) > 0 else False

import itertools
def permutations(array, choose=None):
    if choose is None:
        choose = len(array)
    return list(itertools.permutations(array, choose))

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

t=[]
for ia in range(n):
    s=set()
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.add(ic)
    t.append(s)

icnt=0

from collections import deque
tyn3 = deque()

def pcnt(icnt,ia,t,n,tyn3,icntmax,r,t2,it):
    ia1=ia
    if ia>=n-1:
        icnt2=len(r)
        icntmax=max(icnt2,icntmax)
        if len(tyn3)>0:
            it2=tyn3.pop()
            r.remove(it2)
        ia=ia-1
        return icntmax,ia
    t3=t[ia]-r
    r1=r.copy()
    for it in t3:
        ia=ia1+1
        t2=t[ia]
        r1.add(it)
        tyn3.append(it)
        icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax,r1,t2,it)
    ia=ia+1
    t2=t[ia]
    icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax,r,t2,it)
    return icntmax,ia

ia=-1    
icntmax=0
r=set()
t2=t[0]
it=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax,r,t2,it)

print(icntmax)

Submission status: Time Limit Exceeded

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

#a.sort()
#c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append(s)
#    print(s)
    
#t.sort()
#print("t: ",t)

icnt=0

#import queue
#tyn3 = queue.Queue()

from collections import deque
tyn3 = deque()

# FIFOキューの作成
#    q.put(i)
#    q.get()

def pcnt(icnt,ia,t,n,tyn3,icntmax):
#    print("icnt:",icnt," ia:",ia," n:",n," icntmax:",icntmax,",",t[ia][1],",",tyn2)
    ia1=ia
    if ia>=n-1:
        icntmax=max(icnt,icntmax)
#        print("return icnt:",icnt," icntmax:",icntmax,tyn2)
        if len(tyn3)>0:
            tyn3.pop()
        ia=ia-1
        return icntmax,ia
#    print(ia)
    icnt1=icnt
    for it in t[ia]:
        ia=ia1+1
        if not it in tyn3:
            icnt=icnt1+1
#            tyn3.put(it)
            tyn3.append(it)
            icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
    ia=ia+1
    icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
#    tyn2.pop(-1)
    return icntmax,ia

ia=-1    
icntmax=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)

print(icntmax)

Submission status: Time Limit Exceeded

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append([len(s),s])
#    print(s)
    
#t.sort()
#print("t: ",t)

tyn2=[]
icnt=0

#import queue
#tyn3 = queue.Queue()

from collections import deque
tyn3 = deque()

# FIFOキューの作成
#    q.put(i)
#    q.get()

def pcnt(icnt,ia,t,n,tyn3,icntmax):
#    print("icnt:",icnt," ia:",ia," n:",n," icntmax:",icntmax,",",t[ia][1],",",tyn2)
    ia1=ia
    if ia>=n-1:
        icntmax=max(icnt,icntmax)
#        print("return icnt:",icnt," icntmax:",icntmax,tyn2)
        if len(tyn3)>0:
            tyn3.pop()
        ia=ia-1
        return icntmax,ia
#    print(ia)
    icnt1=icnt
    for it in t[ia][1]:
        ia=ia1+1
        if not it in tyn3:
            icnt=icnt1+1
#            tyn3.put(it)
            tyn3.append(it)
            icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
    ia=ia+1
    icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
#    tyn2.pop(-1)
    return icntmax,ia

ia=-1    
icntmax=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)

print(icntmax)

Submission status: Time Limit Exceeded

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append([len(s),s])
#    print(s)
    
t.sort()
#print("t: ",t)

tyn2=[]
icnt=0

#import queue
#tyn3 = queue.Queue()

from collections import deque
tyn3 = deque()

# FIFOキューの作成
#    q.put(i)
#    q.get()

def pcnt(icnt,ia,t,n,tyn3,icntmax):
#    print("icnt:",icnt," ia:",ia," n:",n," icntmax:",icntmax,",",t[ia][1],",",tyn2)
    ia1=ia
    if ia>=n-1:
        icntmax=max(icnt,icntmax)
#        print("return icnt:",icnt," icntmax:",icntmax,tyn2)
        if len(tyn3)>0:
            tyn3.pop()
        ia=ia-1
        return icntmax,ia
#    print(ia)
    icnt1=icnt
    for it in t[ia][1]:
        ia=ia1+1
        if not it in tyn3:
            icnt=icnt1+1
#            tyn3.put(it)
            tyn3.append(it)
            icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
    ia=ia+1
    icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)
#    tyn2.pop(-1)
    return icntmax,ia

ia=-1    
icntmax=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax)

print(icntmax)

Submission status: Time Limit Exceeded

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append([len(s),s])
#    print(s)
    
t.sort()
#print("t: ",t)

tyn2=[]
icnt=0

def pcnt(icnt,ia,t,n,tyn2,icntmax):
#    print("icnt:",icnt," ia:",ia," n:",n," icntmax:",icntmax,",",t[ia][1],",",tyn2)
    ia1=ia
    if ia>=n-1:
        icntmax=max(icnt,icntmax)
#        print("return icnt:",icnt," icntmax:",icntmax,tyn2)
        if len(tyn2)>0:
            tyn2.pop(-1)
        ia=ia-1
        return icntmax,ia
#    print(ia)
    icnt1=icnt
    for it in t[ia][1]:
        ia=ia1+1
        if not it in tyn2:
            icnt=icnt1+1
            tyn2.append(it)
            icntmax,ia=pcnt(icnt,ia,t,n,tyn2,icntmax)
    ia=ia+1
    icntmax,ia=pcnt(icnt,ia,t,n,tyn2,icntmax)
#    tyn2.pop(-1)
    return icntmax,ia

ia=-1    
icntmax=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn2,icntmax)

print(icntmax)

Submission status: Time Limit Exceeded

Solution code:
import itertools

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort()

#n = 3
#    n = int(input())
lis = [x for x in range(n)] # 0からn-1までのリスト
 
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成
# 以下出力
icmax=0
for one_case in permutations_lis: 
#    print(list(one_case))
    icnt=0
    for i in range(n):
        ii=one_case[i]
        if a[i][0]<c[ii][0] and a[i][1]<c[ii][1]:
            icnt=icnt+1
    if icmax<icnt:
        icmax=icnt

print(icmax)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]

agg = [list() for _ in range(n)]
for i in range(n):
    c, d = blue[i]
    for j in range(n):
        a, b = red[j]
        if c > a and d > b:
            agg[i].append(j)

prod = itertools.product(*[x for x in agg if len(x) > 0])
res = 0
for p in prod:
    res = max(res, len(set(p)))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def dfs(i=0, cnt=0):
        if i == n: return cnt
        bx, by = b[i]
        res = dfs(i + 1, cnt)
        for j in range(n):
            if fin[j]: continue
            rx, ry = r[j]
            if rx >= bx: break
            if ry < by:
                fin[j] = True
                tmp = dfs(i + 1, cnt + 1)
                fin[j] = False
                res = max(res, tmp)
        return res

    n = int(input())
    r = [list(map(int, input().split())) for _ in range(n)]
    b = [list(map(int, input().split())) for _ in range(n)]
    r.sort(key=itemgetter(0, 1))
    b.sort(key=itemgetter(0, 1))
    # print(r)
    # print(b)
    fin = [False] * n
    print(dfs())

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
red = [list(map(int,input().split())) for _ in range(n)]
blue = [list(map(int,input().split())) for _ in range(n)]
red_count = []
import copy

for i in range(n):
  index_list = []
  for j in range(n):
    if blue[j][0]>red[i][0] and blue[j][1]>red[i][1]:
      index_list.append(j)
  red_count.append(index_list)
red_count.sort(key=lambda x: len(x))

def redcounter(count,i,red_count):
  if i == len(red_count)-1 and red_count[i]:
    return count+1
  elif  i == len(red_count)-1:
    return count
  
  if red_count[i]:
    for index in range(len(red_count[i])): ## removeするindex
      remove_index = red_count[i][index]
      red_count_copy = copy.deepcopy(red_count)
      c = count
      for j in range(i+1,len(red_count_copy)): ## removeしていく
        if remove_index in red_count_copy[j]:
          red_count_copy[j].remove(remove_index)
      c = max(count,redcounter(c,i+1,red_count_copy))
    return c+1
  else:
    return redcounter(count,i+1,red_count)
   
print(redcounter(0,0,red_count))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    red, blue = [], []
    for _ in range(N):
        a, b = map(int, input().split())
        red.append([a, b])
    for _ in range(N):
        a, b = map(int, input().split())
        blue.append([a, b])

    d = dict()
    for i in range(N):
        for j in range(N):
            if blue[i][0] > red[j][0] and blue[i][1] > red[j][1]:
                if i not in d:
                    d[i] = [j]
                else:
                    d[i].append(j)

    cur = dict()
    cur[0] = 0
    for i in d:
        temp = dict()
        for c in cur:
            for j in d[i]:
                if (c >> j) % 2 != 1:
                    cnew = c | (1 << j)
                    if cnew not in cur:
                        temp[cnew] = cur[c] + 1
        for c in temp:
            cur[c] = temp[c]
    return max(cur.values())

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import itertools
from itertools import permutations
N=int(input())
ab=list(list(map(int,input().split())) for _ in range(N))
cd=list(list(map(int,input().split())) for _ in range(N))
perab=list(itertools.permutations(ab,N))
l=[[0] for _ in range(len(perab))]
for mab in perab:
    for i in range(N):
        if cd[i][0]-mab[i][0]>0 and cd[i][1]-mab[i][1]>0:
            l[perab.index(mab)].append(1)
print(max(sum(ml) for ml in l))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
r=[list(map(int, input().split())) + [set()] for _ in range(N)]
for _ in range(N):
	bx,by=map(int, input().split())
	for rx,ry,s in r:
		if bx>rx and by>ry:
			s.add(bx)
r=sorted(r, key=lambda x: len(x[2]))
def find(i, c, sel):
	if i == N:
		return c
	return max([find(i+1, c, sel)] + [find(i+1, c+1, sel | set([s])) for s in r[i][2] if s not in sel])
print(find(0, 0, set()))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import random
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    red = [[a + b, a, b] for a, b in (LI() for _ in range(n))]
    blue = [[a + b, a, b] for a, b in (LI() for _ in range(n))]

    ans = 0
    red.sort()
    for _ in range(n):
        red = red[-1:] + red[:-1]
        used = [0] * n
        res = 0
        for s, a, b in red:
            near = -1
            d = INF
            for i, (ss, x, y) in enumerate(blue):
                if a < x and b < y:
                    tmp = x - a + y - b
                    if tmp < d and not used[i]:
                        near = i
                        d = tmp

            if near != -1:
                used[near] = 1
                res += 1
        ans = max(ans, res)

    red.reverse()
    for _ in range(n):
        red = red[-1:] + red[:-1]
        used = [0] * n
        res = 0
        for s, a, b in red:
            near = -1
            d = INF
            for i, (ss, x, y) in enumerate(blue):
                if a < x and b < y:
                    tmp = x - a + y - b
                    if tmp < d and not used[i]:
                        near = i
                        d = tmp

            if near != -1:
                used[near] = 1
                res += 1
        ans = max(ans, res)

    for _ in range(20):
        random.shuffle(red)
        for _ in range(n):
            red = red[-1:] + red[:-1]
            used = [0] * n
            res = 0
            for s, a, b in red:
                near = -1
                d = INF
                for i, (ss, x, y) in enumerate(blue):
                    if a < x and b < y:
                        tmp = x - a + y - b
                        if tmp < d and not used[i]:
                            near = i
                            d = tmp

                if near != -1:
                    used[near] = 1
                    res += 1
            ans = max(ans, res)

    return ans


print(main())

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,B = [], []
for n in range(N):
    A.append(LI())
for n in range(N):
    B.append(LI())

"""
一旦赤い点がどの青い点を持てるのかを洗い出す
lenが小さい順に青を消していく。
何個消せるかで勝負
"""

b_a = []
for b in B:
    tmp = []
    for a in A:
        if a[0] < b[0] and a[1] < b[1]:
            # 赤が青より小さいとき
            tmp.append(a)
    if tmp:
        b_a.append(tmp)
#  print(b_a)

result = 0
results = []
#  print('ba', b_a)
def dfs(arr, count):
    for i in range(len(arr)-1, -1, -1):
        tmp = sorted(arr, reverse=True, key=lambda x: len(x))
        popped = tmp.pop()
        #  print('popped', popped)
        #  tmp = [_ for _ in arr]
        for p in popped:
            l = [[k for k in j if k != p] for j in tmp]
            l = [j for j in l if j != []]
            #  print('l',l)
            if not l:
                results.append(count+1)
            else:
                dfs(l, count+1)


dfs(b_a, 0)
#  print(results)
if not results:
    print(0)
    exit()
print(max(results))

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,B = [], []
for n in range(N):
    A.append(LI())
for n in range(N):
    B.append(LI())

"""
一旦赤い点がどの青い点を持てるのかを洗い出す
lenが小さい順に青を消していく。
何個消せるかで勝負
"""

b_a = []
for b in B:
    tmp = []
    for a in A:
        if a[0] < b[0] and a[1] < b[1]:
            # 赤が青より小さいとき
            tmp.append(a)
    if tmp:
        b_a.append(tmp)
#  print(b_a)

result = 0
results = []
def dfs(arr, count):
    for i in range(len(arr)-1, -1, -1):
        arr = sorted(arr, reverse=True, key=lambda x: len(x))
        popped = arr.pop()
        for p in popped:
            popped = p
            tmp = [_ for _ in arr]
            tmp = [[k for k in j if k != popped] for j in tmp]
            tmp = [j for j in tmp if j != []]
            if not tmp:
                results.append(count+1)
            else:
                dfs(tmp, count+1)


dfs(b_a, 0)
#  print(results)
if not results:
    print(0)
    exit()
print(max(results))

Submission status: Time Limit Exceeded

Solution code:
import copy

inf=1<<60
N=int(input())
ab=[]
cd=[]
for i in range(N):
    ab.append(tuple(map(int,input().split())))
for i in range(N):
    cd.append(tuple(map(int,input().split())))
ab.sort()
cd.sort()

def solve(n,rest_cd,matched):
    #print('solve ',n,matched)
    if n==N:
        return matched
    matched2=max(matched,solve(n+1,rest_cd,matched))
    filtered=list(filter(lambda t:ab[n][0] < t[0] and ab[n][1] < t[1], rest_cd))
    if len(filtered)==0:
        return matched
    maxc = min(filtered, key=lambda x:x[1])[0]
    maxd = min(filtered, key=lambda x:x[0])[1]
    filtered=filter(lambda t:t[0] <= maxc and t[1] <= maxd, filtered)
    for f in filtered:
        rest_cd2 = copy.copy(rest_cd)
        rest_cd2.remove(f)
        matched2=max(matched2,solve(n+1,rest_cd2,matched+1))
        #print(ab[n],f,matched2)
    return matched2

print(solve(0,cd,0))

Submission status: Time Limit Exceeded

Solution code:
inf=1<<60
N=int(input())
ab=[]
cd=[]
for i in range(N):
    ab.append(tuple(map(int,input().split())))
for i in range(N):
    cd.append(tuple(map(int,input().split())))
ab.sort()
cd.sort()

def solve(n,rest_cd,matched):
    #print('solve ',n,matched)
    if n==N:
        return matched
    matched2=max(matched,solve(n+1,rest_cd,matched))
    filtered=list(filter(lambda t:ab[n][0] < t[0] and ab[n][1] < t[1], rest_cd))
    if len(filtered)==0:
        return matched
    maxc = min(filtered, key=lambda x:x[1])[0]
    maxd = min(filtered, key=lambda x:x[0])[1]
    filtered=filter(lambda t:t[0] <= maxc and t[1] <= maxd, filtered)
    for f in filtered:
        rest_cd2 = rest_cd.copy()
        rest_cd2.remove(f)
        matched2=max(matched2,solve(n+1,rest_cd2,matched+1))
        #print(ab[n],f,matched2)
    return matched2

print(solve(0,cd,0))

Submission status: Time Limit Exceeded

Solution code:
inf=1<<60
N=int(input())
ab=[]
cd=[]
for i in range(N):
    ab.append(tuple(map(int,input().split())))
for i in range(N):
    cd.append(tuple(map(int,input().split())))
ab.sort()
cd.sort()

def solve(n,rest_cd,matched,history):
    #print('solve ',n,matched,history)
    if n==N:
        return matched
    matched2=max(matched,solve(n+1,rest_cd,matched,history))
    filtered=list(filter(lambda t:ab[n][0] < t[0] and ab[n][1] < t[1], rest_cd))
    if len(filtered)==0:
        return matched
    maxc = min(filtered, key=lambda x:x[1])[0]
    maxd = min(filtered, key=lambda x:x[0])[1]
    filtered=filter(lambda t:t[0] <= maxc and t[1] <= maxd, filtered)
    for f in filtered:
        rest_cd2 = rest_cd.copy()
        rest_cd2.remove(f)
        history2 = history.copy()
        history2.append(((ab[n][0],ab[n][1]),f))
        matched2=max(matched2,solve(n+1,rest_cd2,matched+1,history2))
        #print(ab[n],f,matched2)
    return matched2

print(solve(0,cd,0,[]))