Problem:


Score : 500 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq H, W \leq 3 \times 10^5

1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)

1 \leq h_i \leq H

1 \leq w_i \leq W

\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

Sample Output 3

6



Sample input:
2 3 3
2 2
1 1
1 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
h,w,m = map(int, input().split(' '))
li = []
dict1 = {}
dict2 = {}
while m > 0:
    var = list(map(int, input().split(' ')))
    li.append(var)
    m -= 1
for i in li:
    if i[0] not in dict1:
        dict1[i[0]] = 1
    else:
        dict1[i[0]] += 1
    if i[1] not in dict2:
        dict2[i[1]] = 1
    else:
        dict2[i[1]] += 1
max1 = max(dict1, key=dict1.get)
max2 = max(dict2, key=dict2.get)
res = 0
for i in li:
    if i[0] == max1 or i[1] == max2:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
P = []
for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    P.append((h,w))

mh = max(PH, key=PH.count)
mw = max(PW, key=PW.count)

cnt = PH.count(mh) + PW.count(mw)
if (mh, mw) in P:
    cnt -= 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

H, W, M = map(int, input().split())
h = []
w = []
for _ in range(M):
    h_, w_ = map(int, input().split())
    h.append(h_)
    w.append(w_)

most_col = Counter(h).most_common()[0][0]
col_count = Counter(h).most_common()[0][1]

c_index = [i for i, x in enumerate(h) if x == most_col]
new_w = [v for k, v in enumerate(w) if k not in c_index]

if len(new_w) == 0:
    print(col_count)
    exit()
    
row_count = Counter(new_w).most_common()[0][1]

ans = col_count + row_count

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,M = [int(x) for x in input().split()]
hw = []
hNum = [0]*H
wNum = [0]*W

for i in range(M):
    h,w = [int(x) for x in input().split()]
    hw.append([h,w])
    hNum[h-1]+=1
    wNum[w-1]+=1

hmax = max(hNum)
hMaxList = []
wmax = max(wNum)
wMaxList = []

for i in range(H):
    if(hmax == hNum[i]):
        hMaxList.append(i)
for i in range(W):
    if(wmax == wNum[i]):
        wMaxList.append(i)

ans = wmax + hmax -1
if((M <= H and hmax ==  1) or (M <= W and wmax ==  1 )):
    ans += 1
# print("aaa",wmax,hmax)
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys,threading
import math
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**5)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]

def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

def main():
    n,m,q=inar()
    row={}
    column={}
    arr=[]
    take1=defaultdict(int)
    take2=defaultdict(int)
    for i in range(q):
        r,c=inar()
        take1[r]+=1
        take2[c]+=1
        arr.append([r,c])
        arr.append([r,c])
        if r not in row:
            row[r]=defaultdict(int)
            row[r][c]+=1
        else:
            row[r][c]+=1
        if c not in column:
            column[c]=defaultdict(int)
            column[c][r]+=1
        else:
            column[c][r]+=1
    ans=0
    take1=dict(sorted(take1.items(),key=operator.itemgetter(1),reverse=True))
    take2 = dict(sorted(take2.items(), key=operator.itemgetter(1), reverse=True))
    # print(take1)
    # print(take2)
    # for i in range(len(take1)):
    #     for j in range(len(take2)):
    for key,item in take1.items():
        r=key
        break
    for key,item in take2.items():
        c=key
        break

    temp=len(row[r])
    temp+=len(column[c])
    temp-=row[r][c]
    ans=max(ans,temp)
    for i in range(q):
        r,c=arr[i][0],arr[i][1]
        temp = len(row[r])
        temp += len(column[c])
        temp -= row[r][c]
        ans = max(ans, temp)

    print(ans)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()
    #threadin.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    H, W, M = MI()
    h = [0] * M
    w = [0] * M
    H_N = defaultdict(int)
    W_N = defaultdict(int)
    MAX_H = 0
    MAX_W = 0
    dic = {}

    for i in range(M):
        h[i], w[i] = MI()
        H_N[h[i]] += 1
        W_N[w[i]] += 1
        MAX_H = max(MAX_H, H_N[h[i]])
        MAX_W = max(MAX_W, W_N[w[i]])
        dic[(h[i], w[i])] = True

    h_max_keys = []
    for k, v in H_N.items():
        if v == MAX_H:
            h_max_keys.append(k)

    w_max_keys = []
    for k, v in W_N.items():
        if v == MAX_W:
            w_max_keys.append(k)

    for h in h_max_keys:
        for w in w_max_keys:
            if (h, w) not in dic:
                print(MAX_H + MAX_W)

    print(MAX_H + MAX_W - 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W,M=map(int,input().split())

if H<=1000 and W<=1000:
  L=np.zeros((H,W), dtype=np.int64)

  for _ in range(M):
    h,w=map(int,input().split())
    L[h-1][w-1]=1
  a=np.sum(L,axis=0)
  b=np.sum(L,axis=1)
  aa,bb=np.meshgrid(a,b)
  ans=(aa+bb-L).max()
else:
  L_H=np.zeros((H),dtype=np.int64)
  L_W=np.zeros((W),dtype=np.int64)
  for _ in range(M):
    h,w=map(int,input().split())
    L_H[h-1]+=1
    L_W[w-1]+=1
  ans=(max(L_H)+max(L_W)-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

h, w, m = list(map(int, input().split()))
bh = np.asarray([0]*h)
bw = np.asarray([0]*w)
bhw = np.asarray([[0]*w]*h)
hmaxs = []
wmaxs = []

for i in range(m):
    h,w = map(int, input().split())
    bh[h-1] +=1
    bw[w-1] +=1
    bhw[h-1][w-1] =1

maxbh= max(bh)
maxbw =max(bw)

for i in range(h):
    if bh[i] == maxbh:
        hmaxs.append(i)

for i in range(w):
    if bw[i] == maxbw:
        wmaxs.append(i)

c =1



for i in hmaxs:
    for j in wmaxs:

        if bhw[i][j]==0:
            c=0

print(maxbh + maxbw -c)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * 2 for i in range(M)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[i] = [hi-1, wi-1]

Hdstmax = max(Hdst)
Wdstmax = max(Wdst)
Hbomb = [i for i, x in enumerate(Hdst) if x == Hdstmax]
Wbomb = [i for i, x in enumerate(Wdst) if x == Wdstmax]


if len(Hbomb)*len(Wbomb) == M:
    print(Hdstmax + Wdstmax - 1)
else:
    print(Hdstmax + Wdstmax)

Submission status: Wrong Answer

Solution code:
import numpy
h,w,m=map(int,input().split())
h_arr=[0]*h
w_arr=[0]*w
record = set()
for i in range(m):
    tmp_h, tmp_w = map(int,input().split())
    record.add((tmp_h,tmp_w))
    h_arr[tmp_h-1] += 1
    w_arr[tmp_w-1] += 1
#最大の列と行の交差点に爆破対象があるかどうかがわからない?
max_h = max(h_arr)
max_w = max(w_arr)
max_h_indexes = [i for i, x in enumerate(h_arr) if x == max_h]
max_w_indexes = [i for i, x in enumerate(w_arr) if x == max_w]
ans = max_h + max_w -1
#たぶんindexesが多いときにTLEになってるんじゃないか
for i in max_h_indexes:
    for j in max_w_indexes:
        if not((i+1,j+1) in record):
            ans += 1
            break
        else:
            continue
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


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


def main():
    h, w, m = [int(i) for i in input().split()]
    d_h = defaultdict(int)
    d_w = defaultdict(int)
    bom = set()
    for _ in range(m):
        h, w = [int(i) for i in input().split()]
        bom.add((h, w))
        d_h[h] += 1
        d_w[w] += 1
    H = sorted(d_h.items(), key=lambda x: -x[1])
    W = sorted(d_w.items(), key=lambda x: -x[1])
    ans = H[0][1] + W[0][1]
    if (H[0][0], W[0][0]) in bom:
        ans -= 1
    try:
        ans2 = H[1][1] + W[0][1]
        if (H[1][0], W[0][0]) in bom:
            ans2 -= 1
    except BaseException:
        ans2 = -1
    try:
        ans3 = H[0][1] + W[1][1]
        if (H[0][0], W[1][0]) in bom:
            ans3 -= 1
    except BaseException:
        ans3 = -1
    print(max(ans, ans2, ans3))

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, W, M = list(map(int, input().split()))
bombs = []
h = {}
w = {}
for i in range(M):
    x, y = list(map(int, input().split()))
    if x in h:
        h[x] += 1
    else:
        h[x] = 1
    if y in w:
        w[y] += 1
    else:
        w[y] = 1
    bombs.append([x, y])

ans = 0
max = 0
for x in range(H, 0, -1):
    if x not in h:
        break
    for y in range(W, 0, -1):
        if y not in w:
            break
        ans = h[x] + w[y]
        if [x, y] in bombs:
            ans -= 1
        if ans > max:
            max = ans

print(max)

Submission status: Wrong Answer

Solution code:
import collections
import sys

*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    return data.pop()

h, w, m = inp(), inp(), inp()


targets = set()
xs = []
ys = []
for _ in range(m):
    y, x = inp(), inp()
    # y -= 1
    # x -= 1
    ys.append(y)
    xs.append(x)
    targets.add((y, x))

x_stat = collections.Counter(xs)
y_stat = collections.Counter(ys)

xs = sorted(set(xs), key=lambda obj: x_stat[obj], reverse=True)
ys = sorted(set(ys), key=lambda obj: y_stat[obj], reverse=True)

mx_x = x_stat[xs[0]]
mx_y = y_stat[ys[0]]
while xs and x_stat[xs[-1]] < x_stat[xs[0]]:
    xs.pop()
while ys and y_stat[ys[-1]] < y_stat[ys[0]]:
    ys.pop()
best_res = 0
# print(xs, x_stat)
# print(ys, y_stat)

for x in xs:
    for y in ys:
        cur = x_stat[x] + y_stat[y] - ((y, x) in targets)
        best_res = max(cur, best_res)
        if mx_x * mx_y == best_res:
            break
print(best_res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    H, W, M = map(int, input().split())

    num_row = [[0, 0] for _ in range(H)]
    set_row = {row: set() for row in range(H)}
    num_col = [[0, 0] for _ in range(W)]
    set_col = {col: set() for col in range(W)}

    for i in range(M):
        h, w = map(int, input().split())
        h -= 1
        w -= 1
        num_row[h][0] += 1
        num_col[w][0] += 1
        num_row[h][1] = h
        num_col[w][1] = w
        set_row[h].add((h,w))
        set_col[w].add((h,w))
    # print(num_row)
    # print(num_col)
    # print(set_row)
    # print(set_col)
    num_row.sort(reverse=True, key=lambda x: x[0])
    num_col.sort(reverse=True, key=lambda x: x[0])
    b_row, idx_row = num_row[0]
    b_col, idx_col = num_col[0]

    max_set_col = set_col[idx_col]
    max_set_row = set_row[idx_row]

    tmp = 0
    for num_r in num_row:
        if max_set_col & set_row[num_r[1]]:
            tmp = max(b_col + num_r[0] - 1, tmp)
        else:
            tmp = max(tmp, num_r[0] + b_row)
    for num_c in num_col:
        if max_set_row & set_col[num_c[1]]:
            tmp = max(b_row + num_c[0] -1, tmp)
        else:
            tmp = max(tmp, num_c[0]+b_col)
    print(tmp)


main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,M = map(int,input().split( ))
Hs = [0 for _ in range(H)]
Ws = [0 for _ in range(W)]
hws = []
for _ in range(M):
    h,w = map(int,input().split( ))
    hws.append([h-1,w-1])
    Hs[h-1] += 1
    Ws[w-1] += 1
hw = [np.argmax(Hs),np.argmax(Ws)]
mh = max(Hs)
mw = max(Ws)
hs = [i for i, x in enumerate(Hs) if x == mh]
ws = [i for i, x in enumerate(Ws) if x == mw]
in_out = 0
for h in hs:
    for w in ws:
        if not([h,w] in hws):
            in_out = 1
if not(hw in hws):
    print(mh + mw - 1)
else:
    print(mh + mw)

Submission status: Wrong Answer

Solution code:
h,w,m = map(int,input().split())
hli = [0]*h
wli = [0]*w
li = []
for i in range(m):
    a,b = map(int,input().split())
    li.append([a,b])
    hli[a-1] += 1
    wli[b-1] += 1
a = max(hli)
b = max(wli)
ans1 = hli.index(a) + 1
ans2 = wli.index(b) + 1
hli2 = []
wli2 = []
for i in range(h):
    if hli[i] == a:
        hli2.append(a)
for i in range(w):
    if wli[i] == b:
        wli2.append(b)
for i in range(len(hli2)):
    for j in range(len(wli2)):
        if [hli2[i]+1,wli2[j]+1] not in li:
            print(a + b)
            exit()
print(a + b - 1)

Submission status: Wrong Answer

Solution code:
import copy


H, W, M = map(int, input().split())
hw1 = [tuple(map(int, input().split())) for _ in range(M)]
hw2 = copy.deepcopy(hw1)
ans1 = 0
ans2 = 0

# hから見る
h_cnt = [0 for _ in range(3*10**5 + 3)]

for h, w in hw1:
    h_cnt[h] += 1

h_max = -1
h_idx = 999999999999

for i in range(len(h_cnt)):
    if h_cnt[i] > h_max:
        h_max = h_cnt[i]
        h_idx = i


L = []
for i in range(len(hw1)):
    h, w = hw1[i]
    if h == h_idx:
        ans1 += 1
        L.append(hw1[i])

hw1 = list(set(hw1) - set(L))

w_cnt = [0 for _ in range(3*10**5 + 3)]
for h, w in hw1:
    w_cnt[w] += 1

w_max = -1
w_idx = 999999999999
for i in range(len(w_cnt)):
    if w_cnt[i] > w_max:
        w_max = w_cnt[i]
        w_idx = i
for h, w in hw1:
    if w == w_idx:
        ans1 += 1


# wから見る
w_cnt = [0 for _ in range(3*10**5 + 3)]

for h, w in hw2:
    h_cnt[w] += 1

w_max = -1
w_idx = 999999999999

for i in range(len(w_cnt)):
    if w_cnt[i] > w_max:
        w_max = w_cnt[i]
        w_idx = i


L = []
for i in range(len(hw2)):
    h, w = hw2[i]
    if w == w_idx:
        ans2 += 1
        L.append(hw2[i])

hw2 = list(set(hw2) - set(L))

h_cnt = [0 for _ in range(3*10**5 + 3)]
for h, w in hw2:
    h_cnt[h] += 1

h_max = -1
h_idx = 999999999999
for i in range(len(h_cnt)):
    if h_cnt[i] > h_max:
        h_max = h_cnt[i]
        h_idx = i
for h, w in hw2:
    if h == h_idx:
        ans2 += 1


print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

h, w, m = map(lambda x: int(x), input().split())

y_to_num = defaultdict(int)
x_to_num = defaultdict(int)

# y_indexes = set()
# x_indexes = set()
y_to_sum = defaultdict(set)


for _ in range(m):
    h, w = map(lambda x: int(x), input().split())
    y_to_num[h] += 1
    x_to_num[w] += 1
    
    y_to_sum[h].add(h + w)
    
# print(y_to_num, x_to_num)
    
# for y, num_y in y_to_num:
#     for x, num_x in x_to_num:

max_num = 0
  
for y in range(h):
    for x in range(w):
        num = y_to_num[y+1] + x_to_num[x+1]
        if x+y+2 in y_to_sum[y+1]:
            num -= 1
        max_num = max(max_num, num)
        
print(max_num)