Submission #815763

#	Time	Username	Problem	Language	Result	Execution time	Memory
815763		beaconmc	Garden (JOI23_garden)	Pypy 3	0 / 100	3084 ms	210664 KiB

garden

from itertools import combinations
from bisect import *
import sys
input = lambda: sys.stdin.readline().strip()

n,m,d = map(int, input().split())

def merge(a,b):
    l = 0
    r = 0

    ans = []
    while not (l==len(a) and r==len(b)):
        if l == len(a):
            ans.append(b[r])
            r += 1

        elif r == len(b):
            ans.append(a[l])
            l += 1
        
        else:
            if a[l] <= b[r]:
                ans.append(a[l])
                l += 1
            else:
                ans.append(b[r])
                r += 1
    return ans
            
        

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

for i in range(m):
    x,y = map(int, input().split())
    b.append([x,y])
    

X = []
Y = []


for i in a:
    X.append(i[0])
    Y.append(i[1])
X.sort()
Y.sort()

ans = 1000000000

for i in range(2**(len(b))):
    x1 = list(X)
    y1 = list(Y)
    tempx = []
    tempy = []
    for j in range(len(b)):
        if (i&(2**j)):
            tempx.append(b[j][0])

        else:
            tempy.append(b[j][1])
    tempx.sort()
    tempy.sort()
            
    x = merge(x1, tempx)
    y = merge(y1, tempy)
    
    

    xx = 1000000000
    yy = 1000000000

    for i in range(len(x)-1):
        xx = min(xx, d-(x[i+1]-x[i])+1)
    xx = min(xx, x[-1]-x[0]+1)

    for i in range(len(y)-1):
        yy = min(yy, d-(y[i+1]-y[i])+1)
    yy = min(yy, y[-1]-y[0]+1)

    ans = min(ans, xx*yy)

print(ans)

    

• Subtask 1: 0 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25