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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/20
Solved on 2019/3/
@author: shinjisu
"""


# ABC 091 C 2D Plane 2N Points
#import math
#import numpy as np

def getInt(): return int(input())

def getIntList(): return [int(x) for x in input().split()]
# def getIntList(): return np.array(input().split(), dtype=np.longlong)

def zeros(n): return [0]*n
# def zeros(n): return np.zeros(n, dtype=np.longlong)

def getIntLines(n): return [int(input()) for i in range(n)]
"""
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data
"""

def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替

def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    #mat = zeros((n, m))
    mat = zeros2(n, m)
    for i in range(n):
        mat[i] = getIntList()
    return mat

ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def makePair(usedR, usedB, cand):
    global Stack
    #d = Debug()
    #d.dmp((usedR, usedB))
    pairCount = 0
    for i in range(len(cand)):
        if cand[i][0] not in usedR and cand[i][1] not in usedB:
            pairCount = max(pairCount,
                            1 + makePair(usedR+[cand[i][0]],
                                         usedB+[cand[i][1]], cand))
    #d.dmp((pairCount))
    return pairCount

def prob():
    global Stack
    Stack = []
    d = Debug()
    d.off()
    N = getInt()
    A = zeros(N)
    C = zeros(N)
    for i in range(N):
        A[i] = tuple(getIntList())
    for i in range(N):
        C[i] = tuple(getIntList())
    d.dmp(N)
    d.dmp(A)
    d.dmp(C)
    red = sorted(A)
    blue = sorted(C)
    d.dmp((red, blue), 'red,blue')
    #candR, candB = zeros(N), zeros(N)
    cand = []
    for i in range(N):
        for j in range(N):
            if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
                cand.append((i, j))
    d.dmp((cand), 'cand')
    usedR, usedB = [], []
    count = makePair(usedR, usedB, cand)
    d.dmp((count), 'count')
    return count


ans = prob()
if ans is None:
    pass
elif type(ans) == list and ans[0] == 1:
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#import math
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m) for i in range(n)]
def getIntLines(n): return [int(input()) for i in range(n)]
def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros2(n, m)
    for i in range(n):
        mat[i] = getIntList()
    return mat


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


class Debug():
    def __init__(self):
        self.debug = True

    def off(self):
        self.debug = False

    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x

def makePair(a, c):
    pairCount = 0
    for e1 in a:
        for e2 in c:
            if e1[0] < e2[0] and e1[1] < e2[1]:
                pairCount = max(pairCount, 1 + makePair(a-set((e1,)), c-set((e2,))))
    return pairCount

def prob():
    d = Debug()
    d.off()
    N = getInt()
    A = zeros(N)
    C = zeros(N)
    for i in range(N):
        A[i] = tuple(getIntList())
    for i in range(N):
        C[i] = tuple(getIntList())
    d.dmp(N)
    d.dmp(A)
    d.dmp(C)
    a = set(A)
    c = set(C)
    d.dmp(a)
    d.dmp(c)
    return makePair(a, c)


ans = prob()
if ans is None:
    pass
elif type(ans) == list and ans[0] == 1:
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(blue, red, ans):
    c = 0
    for i, b in enumerate(blue):
        for j, r in enumerate(red):
            if b[0] >= r[0] and b[1] >= r[1]:
                blue.pop(i)
                red.pop(j)
                c = max(c, f(blue, red, ans + 1))
                blue.insert(i, b)
                red.insert(j, r)
    return max(c, ans)


def main():
    N = int(input())
    red = [list(map(int, input().split())) for _ in range(N)]
    blue = [list(map(int, input().split())) for _ in range(N)]
    print(f(blue, red, 0))


main()

Submission status: Time Limit Exceeded

Solution code:
#ABC091C
import sys
sys.setrecursionlimit(10**6)
N=int(input())
A=[]
B=[]
for n in range(N):
	A.append(list(map(int,input().split())))
for n in range(N):
	B.append(list(map(int,input().split())))
A.sort(key=lambda x:(x[0],x[1]))
B.sort(key=lambda x:(x[0],x[1]))
def DP(ca,cb):
	global A,B,N
	c=0
	d=0
	for b in range(N):
		e=0
		if cb[b]==0:
			continue
		for a in range(N):
			e=0
			if A[a][0]>B[b][0]:
				break
			else:
				if ca[a] and cb[b]:
					if A[a][1]<B[b][1]:
						e=1
						d=1
						c=max(c,DP(ca[:a]+[0]+ca[a+1:],\
							cb[:b]+[0]+cb[b+1:]))
		else:
			if e:
				cb[b]=0
	return c+d
ca=[1 for _ in range(N)]
cb=[1 for _ in range(N)]
print(DP(ca,cb))

Submission status: Time Limit Exceeded

Solution code:
#ABC091C
N=int(input())
A=[]
B=[]
for n in range(N):
	A.append(list(map(int,input().split())))
for n in range(N):
	B.append(list(map(int,input().split())))
A.sort(key=lambda x:(x[0],x[1]))
B.sort(key=lambda x:(x[0],x[1]))
def DP(ca,cb):
	global A,B,N
	c=0
	d=0
	for b in range(N):
		for a in range(N):
			if A[a][0]>B[b][0]:
				break
			else:
				if ca[a] and cb[b]:
					if A[a][1]<B[b][1]:
						d=1
						c=max(c,DP(ca[:a]+[0]+ca[min(N-1,a+1):],\
							cb[:b]+[0]+cb[min(N-1,b+1):]))
	return c+d
ca=[1 for _ in range(N)]
cb=[1 for _ in range(N)]
print(DP(ca,cb))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8

import numpy as np
import random
import copy

def select_ok(r_list,b_position):
    pass_list = []
    for i in range(len(r_list)):
        if r_list[i][0] < b_position[0] and r_list[i][1] < b_position[1]:
            pass_list.append(r_list[i])

    return pass_list



n = int(input())
r = []
b = []

for i in range(n):
    position = list(map(int, input().split()))
    r.append(position)

for i in range(n):
    position = list(map(int, input().split()))
    b.append(position)

b_sorted = sorted(b,key=lambda x:x[0])

answer = 0
for i in range(10000):
    r_2 = copy.copy(r)
    count = 0
    for i in range(n):
        # print(r)
        pass_list = select_ok(r_2,b_sorted[i])
        # pass_list_sorted = sorted(pass_list,key=lambda x:x[0])

        if len(pass_list) > 0:
            count += 1
            delete = random.choice(pass_list)
            r_2.remove(delete)

    answer = max(count,answer)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
aa=[]
a=int(input())
for i in range(0,a):
  aa.append(input().split(" "))

bb=[]
for j in range(0,a):
  bb.append(input().split(" "))
  
pattern=[]
zentai=[]
chouhuku=0

for m in range(0,a**a):
  for n in range(0,a):
    pattern.append(m//(a**n)%a)
  
  for w in range(0,a):
    if pattern.count(pattern[w])>=2:
      chouhuku=1
  
  if chouhuku==0:
    zentai.append(pattern)
  pattern=[]
  chouhuku=0


score=0
max=0

for ww in zentai:
  for z in range(0,a):
    if aa[z][0]<bb[int(ww[z])][0] and aa[z][1]<bb[int(ww[z])][1]:
      score=score+1

  if max<=score:
    max=score
  score=0

print(max)

Submission status: Time Limit Exceeded

Solution code:
aa=[]
a=int(input())
for i in range(0,a):
  aa.append(input().split(" "))

bb=[]
for j in range(0,a):
  bb.append(input().split(" "))

#print(aa)
#print(bb)
  
pattern=[]
zentai=[]
chouhuku=0

for m in range(0,a**a):
  for n in range(0,a):
    pattern.append(m//(a**n)%a)
    
  #print(pattern)
  
  for w in range(0,a):
    if pattern.count(pattern[w])>=2:
      chouhuku=1
  
  if chouhuku==0:
    zentai.append(pattern)
  pattern=[]
  chouhuku=0
  
#print(zentai)

score=0
max=0

for ww in zentai:
  for z in range(0,a):
    if aa[z][0]<bb[int(ww[z])][0] and aa[z][1]<bb[int(ww[z])][1]:
      score=score+1
  #print(ww)
  #print ("score="+str(score))
  if max<=score:
    max=score
  score=0

print(max)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
R = [tuple([int(x) for x in input().split()]) for _ in range(N)]
B = [tuple([int(x) for x in input().split()]) for _ in range(N)]

xl = [set() for _ in range(2 * N + 1)]
yl = [set() for _ in range(2 * N + 1)]

for b in B:
    x, y = b
    for i in range(x):
        xl[i].add(b)
    for j in range(y):
        yl[j].add(b)

cands = []
for r in R:
    x, y = r
    s = xl[x].intersection(yl[y])
    cands.append([r, len(s), s])

def f(cands, used, n):
    if not cands:
        return n
    ret = 0
    hd, tl = cands[0], cands[1:]
    r, _, s = hd
    for t in s - used:
        u = used.union({t})
        ret = max(ret, f(tl, u, n + 1))
    ret = max(ret, f(tl, used, n))
    return ret

import operator
cands.sort(key=operator.itemgetter(1))
print(f(cands, set(), 0))

Submission status: Time Limit Exceeded

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

N = int(input())

abn = []
cdn = []
for i in range(N):
    abn.append(list(map(int, input().split())))
for i in range(N):
    cdn.append(list(map(int, input().split())))

pare_cnt_lst = []
for x in itertools.permutations(abn, N):
    pare_cnt = 0
    for ((a,b),(c,d)) in zip(x,cdn):
        if a < c and b < d:
            pare_cnt += 1

    pare_cnt_lst.append(pare_cnt)

print(max(pare_cnt_lst))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import random

N = int(input())
A = []
B = []
C = []
D = []
E = []
ans = 0
for i in range(0,N):
  H = list(map(int,input().split()))
  A.append(H[0])
  B.append(H[1])
  
for i in range(0,N):
  H = list(map(int,input().split()))
  C.append(H[0])
  D.append(H[1])
  E.append(i)

for i in range(0, 50000):
  random.shuffle(E)
  a = 0
  for j in range(0,N):
    if A[j] < C[E[j]] and B[j] < D[E[j]]:
      a += 1
  ans = max(ans,a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N = int(input())
rn = [list(map(int,input().split())) for _ in range(N)]
bn = [list(map(int,input().split())) for _ in range(N)]
ans = 0
for p in permutations(range(N)):
  ans = max(ans, sum([1 if rn[i][0] < bn[p[i]][0] and rn[i][1] < bn[p[i]][1] else 0 for i in range(N)]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C
n = int(input())
pairs = [[int(s) for s in input().split()] for _ in range(2 * n)]
reds = sorted(pairs[:n])
blues = sorted(pairs[n:])

def f(reds, blues):
    if not reds:
        return 0
    else:
        x, y = reds[-1]
        idxs = [idx for idx, pair in enumerate(blues)
                if x < pair[0] and y < pair[1]]
        if idxs:
            return 1 + max(f(reds[:-1], blues[:idx] + blues[idx+1:]) for idx in idxs)
        else:
            return 0 + f(reds[:-1], blues)
        
print(f(reds, blues))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import numpy as np
N = int(input())
red = np.array([list(map(int, input().split())) for _ in range(N)])
blue = np.array([list(map(int, input().split())) for _ in range(N)])

def shuffle(l):
    for i in permutations(l):
        yield i

def judge(r, b):
    cnt = 0
    for i, j in zip(r, b):
        if i[0] < j[0] and i[1] < j[1]:
            cnt += 1
    return cnt

print(max([judge(red, b) for b in shuffle(blue)]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]

def shuffle(l):
    for i in permutations(l):
        yield i

def judge(r, b):
    cnt = 0
    for i, j in zip(r, b):
        if i[0] < j[0] and i[1] < j[1]:
            cnt += 1
    return cnt

print(max([judge(red, b) for b in shuffle(blue)]))

Submission status: Time Limit Exceeded

Solution code:
def func(k):
	global n
	global f
	global g
	global ee
	if k<n:
		if len(ee[k])==0:
			func(k+1)
			if k==n-1:
				g.append(len(set(f)))
		else:
			for i in range(len(ee[k])):
				f.append(ee[k][i])
				func(k+1)
				if k==n-1:
					g.append(len(set(f)))
				f.pop()

n=int(input())

a=[]
b=[]
for i in range(n):
	s=input().split(" ")
	a.append(int(s[0]))
	b.append(int(s[1]))

c=[]
d=[]
for i in range(n):
	s=input().split(" ")
	c.append(int(s[0]))
	d.append(int(s[1]))

p=0
ee=[]
for i in range(n):
	e=[]
	for j in range(n):
		if a[i]<c[j] and b[i]<d[j]:
			e.append(j)
	ee.append(e)

f=[]
g=[]

func(0)
print(max(g))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = 0
x = []
y = []

for i in range(N):
    s,t = map(int, input().split())
    x.append([s,t])

for j in range(N):
    u,v = map(int, input().split())
    y.append([v,u])

x.reverse()
y.sort()
k = 0
while k < N:
    for l in range(len(x)):
        if x[l][0]<y[k][1] and x[l][1]<y[k][0]:
            a += 1
            del(x[l])
            break
    N += 1

print(a)

Submission status: Time Limit Exceeded

Solution code:
def dfs(a, b, c, d, idx, u, p):
    res = p
    if idx < len(a):
        for i in range(n):
            if i not in u:
                if c[idx] > a[i] and d[idx] > b[i]:
                    u2 = set(u)
                    u2.add(i)
                    res = max(res, dfs(a, b, c, d, idx + 1, u2, p + 1))
                else:
                    res = max(res, dfs(a, b, c, d, idx + 1, u, p))
    return res

n = int(input())
a = [0] * n
b = [0] * n
c = [0] * n
d = [0] * n
for i in range(n):
    ai, bi = [int(x) for x in input().split()]
    a[i] = ai
    b[i] = bi
for i in range(n):
    ci, di = [int(x) for x in input().split()]
    c[i] = ci
    d[i] = di

res = dfs(a, b, c, d, 0, set(), 0)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
red =[]
blue = []

for i in range(N):
  red.append(input().split())
for i in range(N):
  blue.append(input().split())
  
permuted_blue = list(itertools.permutations(blue))

count = []
for id, blue_points in enumerate(permuted_blue):
    count.append(0)
    for i in range(N):
        if count[id] + (N-1) < max(count):
            break
        if (int(blue_points[i][0])-int(red[i][0])>0 and int(blue_points[i][1])-int(red[i][1])>0):
            count[id] += 1
print(max(count))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
red=[]
blue=[]
for i in range(n):
    red.append(list(map(int,input().split())))
for j in range(n):
    blue.append(list(map(int,input().split())))
perm=list(itertools.permutations(blue))
pair=0
ans=0
for k in perm:
    for m in range(n):
        if n-m+pair+1<=ans:
            continue
        if int(red[m][0])<int(k[m][0]) and int(red[m][1])<int(k[m][1]):
            pair+=1
        
    if pair>ans:
        ans=pair
    if ans==n:
        break
    pair=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
red =[]
blue = []

for i in range(N):
  red.append(input().split())
for i in range(N):
  blue.append(input().split())
  
permuted_blue = list(itertools.permutations(blue))

count = []
for id, blue_points in enumerate(permuted_blue):
    count.append(0)
    for i in range(N):
        if (int(blue_points[i][0])-int(red[i][0])>0 and int(blue_points[i][1])-int(red[i][1])>0):
            count[id] += 1
print(max(count))

Submission status: Time Limit Exceeded

Solution code:
import sys


def spam(ab, cd, count=0):
    ab = ab[:]
    cd = cd[:]
    counts = [-1]
    for x in ab:
        for y in cd:
            if x[0] < y[0] and x[1] < y[1]:
                ab_ = ab[:]
                ab_.remove(x)
                cd_ = cd[:]
                cd_.remove(y)
                counts += [spam(ab_, cd_, count + 1)]
    return max([count, max(counts)])


def main():
    N = int(sys.stdin.readline())
    ab = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
    cd = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
    print(spam(ab, cd))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
red_points = []
blue_points = []
pair_cnt = 0


def check(idx, visited):
    global pair_cnt
    if idx == N:
        pair_cnt = max(pair_cnt, visited.count(True))
        return

    red_point = red_points[idx]
    for i in range(N):
        if visited[i]:
            continue

        new_visited = visited[:]
        blue_point = blue_points[i]
        if red_point[0] < blue_point[0] and red_point[1] < blue_point[1]:
            new_visited[i] = True
        check(idx + 1, new_visited)


N = int(input())
for i in range(N):
    a, b = map(int, input().split())
    red_points.append((a, b))
for i in range(N):
    a, b = map(int, input().split())
    blue_points.append((a, b))
check(0, [False for _ in range(N)])
print(pair_cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
red=[]
for i in range(n):
    red.append(list(map(int,input().split())))
blue=[]
for j in range(n):
    blue.append(list(map(int,input().split())))
perm=list(itertools.permutations(blue))
pair=0
ans=0
for k in perm:
    for m in range(n):
        if int(red[m][0])<int(k[m][0]) and int(red[m][1])<int(k[m][1]):
            pair+=1
    if pair>ans:
        ans=pair
    pair=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

res = 0
for _blue in itertools.permutations(blue):
    sum_pair = len([1 for (a, b), (c, d) in zip(red, _blue) if a < c and b < d])
    res = max(res, sum_pair)
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a, b = [], []
for i in range(n):
    a.append(tuple(map(int, input().split())))
for i in range(n):
    b.append(tuple(map(int, input().split())))


def r(a, b):
    result = 0
    for i in range(n):
        if a[i][0] < b[i][0] and a[i][1] < b[i][1]:
            result += 1
    return result


from itertools import permutations

print(max(r(a, b0) for b0 in permutations(b)))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
red_points_x = []
red_points_y = []
blue_points_x = []
blue_points_y = []
for _ in range(N):
    x, y = map(int, input().split())
    red_points_x.append(x)
    red_points_y.append(y)
for _ in range(N):
    x, y = map(int, input().split())
    blue_points_x.append(x)
    blue_points_y.append(y)

ans = 0
for indices in itertools.permutations(range(N)):
    n_pairs = 0
    for i, index in enumerate(indices):
        if red_points_x[i] < blue_points_x[index] and red_points_y[i] < blue_points_y[index]:
            n_pairs += 1
    if n_pairs > ans:
        ans = n_pairs
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
red=[]
blue=[]
for i in range(n):
  a,b=map(int,input().split())
  red.append([a,b])
for j in range(n):
  a,b=map(int,input().split())
  blue.append([a,b])
blue.sort(key=lambda x:x[0])
red.sort(key=lambda x:x[1],reverse=True)

cnt=0
for x,y in blue:
  for i in range(n):
    if red[i][0]<x and red[i][1]<y:
      cnt+=1
      red[i][0]=float("INF")
      red[i][1]=float("INF")
      break
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
class mf_graph:
    n=1
    g=[[] for i in range(1)]
    pos=[]
    def __init__(self,N):
        self.n=N
        self.g=[[] for i in range(N)]
    def add_edge(self,From,To,cap):
        assert 0<=From and From<self.n
        assert 0<=To and To<self.n
        assert 0<=cap
        m=len(self.pos)
        self.pos.append((From,len(self.g[From])))
        self.g[From].append({"to":To,"rev":len(self.g[To]),"cap":cap})
        self.g[To].append({"to":From,"rev":len(self.g[From])-1,"cap":0})
        return m
    def get_edge(self,i):
        m=len(self.pos)
        assert 0<=i and i<m
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[_e["to"]][_e["rev"]]
        return {"from":self.pos[i][0],
                "to":_e["to"],
                "cap":_e["cap"]+_re["cap"],
                "flow":_re["cap"]}
    def edges(self):
        m=len(self.pos)
        result=[]
        for i in range(m):
            result.append(self.get_edge(i))
        return result
    def change_edge(self,i,new_cap,new_flow):
        m=len(self.pos)
        assert 0<=i and i<m
        assert 0<=new_flow and new_flow<=new_cap
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[_e["to"]][_e["rev"]]
        _e["cap"]=new_cap-new_flow
        _re["cap"]=new_flow
    def flow(self,s,t,flow_limit=(2**31)-1):
        assert 0<=s and s<self.n
        assert 0<=t and t<self.n
        level=[0 for i in range(self.n)]
        Iter=[0 for i in range(self.n)]
        que=deque([])
        def bfs():
            for i in range(self.n):
                level[i]=-1
            level[s]=0
            que=deque([])
            que.append(s)
            while(len(que)>0):
                v=que.popleft()
                for e in self.g[v]:
                    if e["cap"]==0 or level[e["to"]]>=0:continue
                    level[e["to"]]=level[v]+1
                    if e["to"]==t:return
                    que.append(e["to"])
        def dfs(func,v,up):
            if (v==s):return up
            res=0
            level_v=level[v]
            for i in range(Iter[v],len(self.g[v])):
                e=self.g[v][i]
                if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue
                d=func(func,e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"]))
                if d<=0:continue
                self.g[v][i]["cap"]+=d
                self.g[e["to"]][e["rev"]]["cap"]-=d
                res+=d
                if res==up:break
            return res
        flow=0
        while(flow<flow_limit):
            bfs()
            if level[t]==-1:
                break
            for i in range(self.n):
                Iter[i]=0
            while(flow<flow_limit):
                f=dfs(dfs,t,flow_limit-flow)
                if not(f):break
                flow+=f
        return flow
    def min_cut(self,s):
        visited=[False for i in range(self.n)]
        que=deque([])
        que.append(s)
        while(len(que)>0):
            p=que.popleft()
            visited[p]=True
            for e in self.g[p]:
                if e["cap"] and not(visited[e["to"]]):
                    visited[e["to"]]=True
                    que.append(e["to"])
        return visited

N=int(input())
G=mf_graph(2*N+2)
s=2*N
t=2*N+1
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    a[i],b[i]=map(int,input().split())
for i in range(N):
    c[i],d[i]=map(int,input().split())
for i in range(N):
    G.add_edge(s,i,1)
    G.add_edge(i+N,t,1)
for i in range(N):
    for j in range(N):
        if a[i]<c[j] and b[i]<d[j]:
            G.add_edge(i,N+j,1)
ans=G.flow(s,t)
print(ans)

Submission status: Accepted

Solution code:
# Ford-Fulkerson algorithm
class FordFulkerson:
  def __init__(self, N):
    self.N = N
    self.edge = [[] for i in range(N)]

  def add_edge(self, fr, to, cap):
    forward = [to, cap, None]
    forward[2] = backward = [fr, 0, forward]
    self.edge[fr].append(forward)
    self.edge[to].append(backward)

  def add_multi_edge(self, v1, v2, cap1, cap2):
    edge1 = [v2, cap1, None]
    edge1[2] = edge2 = [v1, cap2, edge1]
    self.edge[v1].append(edge1)
    self.edge[v2].append(edge2)

  def dfs(self, v, t, f):
    if v == t:
      return f
    used = self.used
    used[v] = 1
    for e in self.edge[v]:
      w, cap, rev = e
      if cap and not used[w]:
        d = self.dfs(w, t, min(f, cap))
        if d:
          e[1] -= d
          rev[1] += d
          return d
    return 0

  def flow(self, s, t):
    flow = 0
    f = INF = 10**9 + 7
    N = self.N
    while f:
      self.used = [0]*N
      f = self.dfs(s, t, INF)
      flow += f
    return flow

import sys
readline = sys.stdin.readline

N = int(input())
R = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]
ff = FordFulkerson(2*N+2)
for v in range(1,N+1):
  ff.add_edge(0,v,1)
for v in range(N):
  ff.add_edge(1+N+v,2*N+1,1)
for u,(a,b) in enumerate(R):
  for v,(c,d) in enumerate(B):
    if a<c and b<d:
      ff.add_edge(1+u,1+N+v,1)
ans = ff.flow(0,2*N+1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab=[]
for i in range(n):
    ab.append(list(map(int, input().split())))
ab = sorted(ab, key=lambda x:x[1], reverse=True)

cd=[]
for i in range(n):
    cd.append(list(map(int, input().split())))
cd = sorted(cd, key=lambda x:x[0])
# print(ab, flush=True)
# print(cd, flush=True)


ans = 0
for i in cd:
    for ji, j in enumerate(ab):
        if i[0]>j[0] and i[1]>j[1]:
            # print(i, j, flush=True)
            ans+=1
            ab.pop(ji)
            break;
print(ans, flush=True)

Submission status: Accepted

Solution code:
"""ABC091 2D Plane 2N Points diff:
"""

N = int(input())

ab = [tuple(map(int, input().split())) for _ in range(N)]
cd = [tuple(map(int, input().split())) for _ in range(N)]

ans_x = 0
cd.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)
ab_used = [0]*N
for i, (c, d) in enumerate(cd):
    for j, (a, b) in enumerate(ab):
        if not ab_used[j] and a < c and b < d:
            ab_used[j] = 1
            ans_x += 1
            break

# ans_y = 0
# cd.sort(key=lambda x: x[1])
# ab.sort(key=lambda x: x[0], reverse=True)
# ab_used = [0]*N
# for i, (c, d) in enumerate(cd):
#     for j, (a, b) in enumerate(ab):
#         if not ab_used[j] and a < c and b < d:
#             ab_used[j] = 1
#             ans_y += 1
#             break

print(ans_x)

Submission status: Accepted

Solution code:
"""ABC091 2D Plane 2N Points diff:
"""

N = int(input())

ab = [tuple(map(int, input().split())) for _ in range(N)]
cd = [tuple(map(int, input().split())) for _ in range(N)]

ans_x = 0
cd.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)
ab_used = [0]*N
for i, (c, d) in enumerate(cd):
    for j, (a, b) in enumerate(ab):
        if not ab_used[j] and a < c and b < d:
            ab_used[j] = 1
            ans_x += 1
            break

ans_y = 0
cd.sort(key=lambda x: x[1])
ab.sort(key=lambda x: x[0], reverse=True)
ab_used = [0]*N
for i, (c, d) in enumerate(cd):
    for j, (a, b) in enumerate(ab):
        if not ab_used[j] and a < c and b < d:
            ab_used[j] = 1
            ans_y += 1
            break

print(max(ans_x, ans_y))

Submission status: Accepted

Solution code:
N = int(input())
ab = [[int(i) for i in input().split()] for _ in range(N)]
cd = [[int(i) for i in input().split()] for _ in range(N)]
 
ab.sort(key = lambda x: x[1], reverse=True)
cd.sort()
 
x = 0
for c, d in cd:
    for a, b in ab:
        if a < c and b < d:
            x += 1
            ab.remove([a, b])
            break
 
print(x)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N = int(input())
R = []
B = []
YFlag = [True]*(2*N)

for _ in range(N):
  a, b = map(int, input().split())
  R.append((a, b))

for _ in range(N):
  c, d = map(int, input().split())
  B.append((c, d))

B.sort()

ans = 0
for c, d in B:
  cand = []
  for a, b in R:
    if a < c and b < d and YFlag[b]:
      cand.append(b)
  if cand:
    ans += 1
    YFlag[max(cand)] = False

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red, blue = [], []
for _ in range(n):
    a, b = map(int, input().split())
    red.append([a, b, min(a, b)])
for _ in range(n):
    a, b = map(int, input().split())
    blue.append([a, b, min(a, b)])
    
red.sort(key=lambda x: x[1])
blue.sort(key=lambda x: x[0])
status = [False for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n-1, -1, -1):
        if not status[j]:
            if red[j][0] < blue[i][0] and red[j][1] < blue[i][1]:
                ans += 1
                status[j] = True
                break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
edges = [[] for _ in range(n)]
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    a, b = ab[i]
    for j in range(n):
        c, d = cd[j]
        if a < c and b < d:
            edges[i].append(j)
matched = [-1] * n
def dfs(v):
    for u in edges[v]:
        if visited[u]:
            continue
        visited[u] = True
        if matched[u] == -1 or dfs(matched[u]):
            matched[u] = v
            return True
    return False

ans = 0
for s in range(n):
    visited = [False] * n
    if dfs(s):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    R = sorted([i_list() for _ in range(n)])
    B = sorted([i_list() for _ in range(n)])

    ans = 0
    for bx, by in B:
        C = [(y,x) for x,y in R if x<bx and y < by]
        if len(C) == 0:
            continue
        ans += 1
        C.sort(reverse=True)
        R.remove([C[0][1],C[0][0]])
    print(ans)


if __name__=="__main__":
    main()