Problem: We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).  Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.  Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Submission attempts (in order):
from random import randint
from collections import defaultdict
#from numba import njit
import numpy as np


def f1(h,w,m,ins):
    
    yp = np.zeros(h,dtype=np.int)
    xp = np.zeros(w,dtype=np.int)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[-1]
    xps = np.argsort(xp)
    y = yp[yps]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        a -= d[yps][xp[xpsi]]
        ans = max(ans,a)
    return ans


def f2(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
    y = yp[yps[0]]
    ans += y[0]
    print(y[0])
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        a -= d[yps[0]][xpsi]
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f2(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


from random import randint
from collections import defaultdict
from numba import njit
import numpy as np


def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            a -= (ypsi,xpsi) in s
            ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


from random import randint
import numpy as np
from numba import njit


@njit('i4(i4,i4,i4,i4[:,:])',cache=True)
def f(h,w,m,ins):
    yp = np.zeros(h,dtype=np.int32)
    xp = np.zeros(w,dtype=np.int32)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = yp[yp.argmax()]
    xpm = xp[xp.argmax()]
    yps = np.where(yp == ypm)[0]
    xps = np.where(xp == xpm)[0]
    ans = yp[yps[0]]+xp[xps[0]]
    for ypsi in yps:
        for xpsi in xps:
            if not ((ypsi,xpsi) in s):
                return ans
    return ans-1


if False:
    while True:
        h,w = randint(1,10**5*3),randint(10**5,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans = f(h,w,m,np.array(ins))
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,np.array([list(map(int,input().split())) for i in range(m)]))
    print(ans)


from random import randint
from collections import defaultdict
import numpy as np

#h,w,m = map(int,input().split())
def f(h,w,m,ins):
    #h,w,m = map(int,input().split())
    
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    
    for hi,wi in ins:
        #hi,wi = map(int,input().split())
        d[hi-1][wi-1] = True
        #b[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
        
    y = yp[yps[0]]
    ans += y[0]
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        #print(a,xpsi,d[yps[0]][xpsi])
        a -= d[yps[0]][xpsi]
        ans = max(ans,a)
    #print(y)
    #print(b)
    return ans

if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ans = f(h,w,m,[(randint(1,h),randint(1,w)) for i in range(m)])
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

from random import randint
from collections import defaultdict
import numpy as np

#h,w,m = map(int,input().split())
def f(h,w,m,ins):
    #h,w,m = map(int,input().split())
    
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0


    
    for hi,wi in ins:
        #hi,wi = map(int,input().split())
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
    ans += yp[yps[0],0]+xp[xps[0],0]
    return ans

if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ans = f(h,w,m,[(randint(1,h),randint(1,w)) for i in range(m)])
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

from random import randint
from collections import defaultdict
from numba import njit
import numpy as np

#h,w,m = map(int,input().split())
def f(h,w,m,ins):
    #h,w,m = map(int,input().split())
    
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    
    for hi,wi in ins:
        #hi,wi = map(int,input().split())
        d[hi-1][wi-1] = True
        #b[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
        
    y = yp[yps[0]]
    ans += y[0]
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        #print(a,xpsi,d[yps[0]][xpsi])
        a -= d[yps[0]][xp[xpsi,1]]
        ans = max(ans,a)
    #print(y)
    #print(b)
    return ans

if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ans = f(h,w,m,[(randint(1,h),randint(1,w)) for i in range(m)])
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

import numpy as np


h,w,m = map(int,input().split())
yp = np.zeros((h,2),dtype=np.int)
yp[:,1] = np.arange(h)
xp = np.zeros((w,2),dtype=np.int)
xp[:,1] = np.arange(w)

b = np.zeros((h,w),dtype=np.bool)


for i in range(m):
    hi,wi = map(int,input().split())
    b[hi-1,wi-1] += 1
    yp[hi-1,0] += 1
    xp[wi-1,0] += 1
yps = np.argsort(yp[:,0])[::-1]
ypmax = yp[yps[0]]
#print(ypmax)
#print(b)
ans = 0
for i in range(h):
    a = xp[i,0]+ypmax[0]
    if b[yps[0],i] == 1:
        a -= 1
    ans = max(ans,a)
print(ans)

import numpy as np


h,w,m = map(int,input().split())
yp = np.zeros((h,2),dtype=np.int)
yp[:,1] = np.arange(h)
xp = np.zeros((w,2),dtype=np.int)
xp[:,1] = np.arange(w)

b = np.zeros((h,w),dtype=np.int)


for i in range(m):
    hi,wi = map(int,input().split())
    b[hi-1,wi-1] += 1
    yp[hi-1,0] += 1
    xp[wi-1,0] += 1
xp[:,0] -= 1
yps = np.argsort(yp[:,0])[::-1]
xps = np.argsort(xp[:,0])[::-1]

#print(xp)
#print(yp)
#print(yps)
#print(xps)

#print(xp)
#print(yp)
#print(b)
ans = yp[yps[0],0]
a = xp[xps[0],0]
ans += a
ans += a==0
print(ans)

from random import randint
from collections import defaultdict
#from numba import njit
import numpy as np


def f1(h,w,m,ins):
    
    yp = np.zeros(h,dtype=np.int)
    xp = np.zeros(w,dtype=np.int)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[-1]
    xps = np.argsort(xp)
    y = yp[yps]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        a -= d[yps][xp[xpsi]]
        ans = max(ans,a)
    return ans


def f2(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
    y = yp[yps[0]]
    ans += y[0]
    print(y[0])
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        a -= d[yps[0]][xpsi]
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f1(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


import numpy as np


h,w,m = map(int,input().split())
yp = np.zeros((h,2),dtype=np.int)
yp[:,1] = np.arange(h)
xp = np.zeros((w,2),dtype=np.int)
xp[:,1] = np.arange(w)

b = np.zeros((h,w),dtype=np.int)


for i in range(m):
    hi,wi = map(int,input().split())
    b[hi-1,wi-1] += 1
    yp[hi-1,0] += 1
    xp[wi-1,0] += 1
yps = np.argsort(yp[:,0])[::-1]
ypmax = yp[yps[0]]
#print(ypmax)
#print(b)
ans = 0
for i in range(h):
    a = xp[i,0]+ypmax[0]
    if b[yps[0],i] == 1:
        a -= 1
    ans = max(ans,a)
print(ans)

from random import randint
from collections import defaultdict
from numba import njit
import numpy as np


def f(h,w,m,ins):
    yp = np.zeros((h),dtype=np.int)
    xp = np.zeros((w),dtype=np.int)
    #yp[:,1] = np.arange(h)
    #xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    
    for hi,wi in ins:
        #d[hi-1][wi-1] = True
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[-1]
    xps = np.argsort(xp)[::-1]
    y = yp[yps]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        #a -= d[yps][xpsi]
        a -= (yps,xpsi) in s
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


from random import randint
from numba.np.ufunc import parallel
import numpy as np
from numba import njit


@njit('i4(i4,i4,i4,i4[:,:])',cache=True)
def f(h,w,m,ins):
    yp = np.zeros(h,dtype=np.int32)
    xp = np.zeros(w,dtype=np.int32)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = yp[yp.argmax()]
    xpm = xp[xp.argmax()]
    yps = np.where(yp == ypm)[0]
    xps = np.where(xp == xpm)[0]
    ans = yp[yps[0]]+xp[xps[0]]
    for ypsi in yps:
        for xpsi in xps:
            if not ((ypsi,xpsi) in s):
                return ans
    return ans-1


if False:
    while True:
        h,w = randint(10**5,10**5*3),randint(10**5,10**5*3)
        m = randint(h*w,10**5*3)
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans = f(h,w,m,np.array(ins,dtype=np.int32))
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,np.array([tuple(map(int,input().split())) for i in range(m)]))
    print(ans)


from random import randint
from collections import defaultdict
#from numba import njit
import numpy as np


def f(h,w,m,ins):
    yp = np.zeros((h),dtype=np.int)
    xp = np.zeros((w),dtype=np.int)
    #yp[:,1] = np.arange(h)
    #xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[-1]
    xps = np.argsort(xp)[::-1]
    y = yp[yps]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        a -= d[yps][xpsi]
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


2 3 3
2 2
1 1
1 3


from random import randint
from collections import defaultdict
#from numba import njit
import numpy as np



def f(h,w,m,ins):
    
    yp = np.zeros(h,dtype=np.int)
    xp = np.zeros(w,dtype=np.int)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[::-1]
    xps = np.argsort(xp)[::-1]
    y = yp[yps[0]]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        a -= d[yps[0]][xp[xpsi]]
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans = f(h,w,m,ins)
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


from random import randint
from collections import defaultdict
#from numba import njit
import numpy as np


def f1(h,w,m,ins):
    
    yp = np.zeros(h,dtype=np.int)
    xp = np.zeros(w,dtype=np.int)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[-1]
    xps = np.argsort(xp)
    y = yp[yps]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        a -= d[yps][xp[xpsi]]
        ans = max(ans,a)
    return ans


def f2(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
    y = yp[yps[0]]
    ans += y[0]
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        a -= d[yps[0]][xpsi]
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f2(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


#from random import randint

def f(h,w,m,ins):
    yp = [0]*h
    xp = [0]*w
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = max(yp)
    xpm = max(xp)
    yps = [i for i in range(h) if yp[i] == ypm]
    xps = [i for i in range(w) if xp[i] == xpm]
    ans = ypm+xpm
    for ypsi in yps:
        for xpsi in xps:
            if not (ypsi,xpsi) in s:
                return ans
    return ans-1

if __name__ == "__main__":
    if False:
        while True:
            h,w = randint(1,10**5*3),randint(10**5,10**5*3)
            m = randint(1,min(h*w,10**5*3))
            ins = [(randint(1,h),randint(1,w)) for i in range(m)]
            ans = f(h,w,m,ins)
            print(ans)
    else:
        h,w,m = map(int,input().split())
        ans = f(h,w,m,[list(map(int,input().split())) for i in range(m)])
        print(ans)


Verdicts: Wrong Answer

Time Limit Exceeded

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted