Submission #815765

#	Time	Username	Problem	Language	Result	Execution time	Memory
815765		beaconmc	Garden (JOI23_garden)	Pypy 3	0 / 100	3071 ms	191264 KiB

garden

from itertools import combinations
n,m,d = map(int, input().split())

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

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

X = []
Y = []

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

ans = 1000000000

for i in range(2**(len(b))):
    x = list(X)
    y = list(Y)
    for j in range(len(b)):
        if (i&(2**j)):
            x.append(b[j][0])
        else:
            y.append(b[j][1])
    x.sort()
    y.sort()
    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