Problem:


Score : 500 points

Problem Statement

On an xy plane, in an area satisfying 0 ≤ x ≤ W, 0 ≤ y ≤ H, there is one house at each and every point where both x and y are integers.

There are unpaved roads between every pair of points for which either the x coordinates are equal and the difference between the y coordinates is 1, or the y coordinates are equal and the difference between the x coordinates is 1.

The cost of paving a road between houses on coordinates (i,j) and (i+1,j) is p_i for any value of j, while the cost of paving a road between houses on coordinates (i,j) and (i,j+1) is q_j for any value of i.

Mr. Takahashi wants to pave some of these roads and be able to travel between any two houses on paved roads only. Find the solution with the minimum total cost.

Constraints

1 ≦ W,H ≦ 10^5

1 ≦ p_i ≦ 10^8(0 ≦ i ≦ W-1)

1 ≦ q_j ≦ 10^8(0 ≦ j ≦ H-1)

p_i (0 ≦ i ≦ W−1) is an integer.

q_j (0 ≦ j ≦ H−1) is an integer.

Input

Inputs are provided from Standard Input in the following form.

W H
p_0
:
p_{W-1}
q_0
:
q_{H-1}

Output

Output an integer representing the minimum total cost.

Sample Input 1

2 2
3
5
2
7

Sample Output 1

29

It is enough to pave the following eight roads.

Road connecting houses at (0,0) and (0,1)

Road connecting houses at (0,1) and (1,1)

Road connecting houses at (0,2) and (1,2)

Road connecting houses at (1,0) and (1,1)

Road connecting houses at (1,0) and (2,0)

Road connecting houses at (1,1) and (1,2)

Road connecting houses at (1,2) and (2,2)

Road connecting houses at (2,0) and (2,1)

Sample Input 2

4 3
2
4
8
1
2
9
3

Sample Output 2

60



Sample input:
2 2
3
5
2
7


Sample output:
29

Submission status: Wrong Answer

Solution code:
from collections import deque



def a_contains_b(a, b):

    for e in b:
        if e not in a:
            return False
    return True

inputs = input().split()
W = int(inputs[0])
H = int(inputs[1])

p = []
q = []
for i in range(W):
    p.append(int(input()))

for i in range(H):
    q.append(int(input()))



##W = 2
##H = 2
##p = [3, 5] # moving horizontally
##q = [2, 7] # moving vertically

##W = 4
##H = 3
##p = [2, 4, 8, 1]
##q = [2, 9, 3]

# list of roads. each road is defined using starting point and ending point
# list of points that should be reachable i.e. every point on the grid

points = []
for j in range(H+1):
    row = []
    for i in range(W+1):
        row.append((i, j))
        points.append((i, j))

##print(points)
num_points = (H+1) * (W+1)

##visited = [['F' for i in range(W)] for j in range(H+1)]


queue = deque()
queue.append(((0, 0), [(0, 0)], 0)) # current point, list of points visited, total cost
##visited[0][0] = 'T'

min_cost = float('inf')
max_path_length = float('-inf')
max_path_costs = []

while queue:
    curr = queue.popleft()
    x = curr[0][0]
    y = curr[0][1]
    path_list = curr[1]
    cost = curr[2]

##    print(path_list)
    n_move = (x, y-1)
    s_move = (x, y+1)
    w_move = (x-1, y)
    e_move = (x+1, y)

    num_moves = 0
    # N
    if y - 1 >= 0 and n_move not in path_list:
        z = list(path_list)
        z.append(n_move)
        queue.append((n_move, z, cost + q[y-1]))
        num_moves += 1

    # S
    if y + 1 <= H and s_move not in path_list:
        z = list(path_list)
        z.append(s_move)
        queue.append((s_move, z, cost + q[y]))
        num_moves += 1

    # E
    if x + 1 <= W and e_move not in path_list:
        z = list(path_list)
        z.append(e_move)
        queue.append((e_move, z, cost + p[x]))
        num_moves += 1

    # W
    if x - 1 >= 0 and w_move not in path_list:
        z = list(path_list)
        z.append(w_move)
        queue.append((w_move, z, cost + p[x-1]))
        num_moves += 1

##    if cost == 60:
##        print(path_list)
##        print(points)

    # if we cannot move anywhere else and all points have been visited, then we check length
    if a_contains_b(path_list, points):
##        print(path_list)

##        if len(path_list) > max_path_length:
##            max_path_costs = [cost]
##            max_path_length = len(path_list)
##        elif len(path_list) == max_path_length:
        max_path_costs.append(cost)
            
            


##print(max_path_costs)      
print(min(max_path_costs))





    ##        if cost < min_cost:
##            print('path_list: {}'.format(path_list))
##            print('cost: {}'.format(cost))
##            min_cost = cost

Submission status: Wrong Answer

Solution code:
w, h = map(lambda x:int(x) , raw_input().split())

INF = 1000000000
MAX_V = (w + 1) * (h + 1)
cost = [[INF for _ in range(MAX_V)] for _ in range(MAX_V)]
mincost = [INF for _ in range(MAX_V)]
used = [False for _ in range(MAX_V)]

def prim():
    mincost[0] = 0
    res = 0

    while True:
        v = -1
        for u in range(MAX_V):
            if (not used[u] and (v == -1 or mincost[u] < mincost[v])):
                v = u

        if v == -1:
            break

        used[v] = True
        res += mincost[v]

        for u in range(MAX_V):
            mincost[u] = min(mincost[u], cost[v][u])

    return res

p = [input() for _ in range(w)]
q = [input() for _ in range(h)]

for x in range(w):
    for y in range(h):
        cost[x * h + y][(x + 1) * h + y] = p[x]
        cost[(x + 1) * h + y][x * h + y] = p[x]
        cost[x * h + y][x * h + (y + 1)] = q[y]
        cost[x * h + (y + 1)][x * h + y] = q[y]
print cost
print prim()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
line = raw_input()
fields = line.split()
W = int(fields[0])
H = int(fields[1])
wp = []
hq = []
for i in xrange(0, W):
	pi = int(raw_input())
	wp.append(pi)

for i in xrange(0, H):
	qj = int(raw_input())
	hq.append(qj)
	
get_houses = []
for i in xrange(0, W + 1):
	unit = []
	for j in xrange(0, H + 1):
		unit.append(False)
	get_houses.append(unit)

costs = []
for i in xrange(0, W + 1):
	unit = []
	for j in xrange(0, H + 1):
		unit.append(-1)
	costs.append(unit)

get_houses[0][0] = True
board_houses = set()
board_houses.add((0, 0))
total = 0
get_num = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
next_dict = {}
while get_num <= (W + 1) * (H + 1):
	for h in board_houses:
		i = h[0]
		j = h[1]
		for index in xrange(0, 4):
			ii = i + dx[index]
			jj = j + dy[index]
			if ii < 0 or ii > W or jj < 0 or jj > H:
				continue
			if get_houses[ii][jj]:
				continue
			cost = costs[ii][jj]
			if index == 0:
				if cost == -1 or cost > wp[ii]:
					costs[ii][jj] = wp[ii]
			
			elif index == 1:
				if cost == -1 or cost > wp[i]:
					costs[ii][jj] = wp[i]

			elif index == 2:
				if cost == -1 or cost > hq[jj]:
					costs[ii][jj] = hq[jj]
			else:
				if cost == -1 or cost > hq[j]:
					costs[ii][jj] = hq[j]

			next_dict[ii * (W + 1) + jj] = costs[ii][jj]
	min_key = 0
	min_value = -1
	if len(next_dict) == 0:
		break
	for key, value in next_dict.items():
		if min_value == -1 or min_value > value:
			min_key = key
			min_value = value 

	xx = min_key / (W + 1)
	yy = min_key % (W + 1)


	board_houses.add((xx, yy))
	total += min_value
	get_num += 1
	get_houses[xx][yy] = True

print total

Submission status: Wrong Answer

Solution code:
import bisect
cost = 0
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
sum_p = []
for i in xrange(W):
    tmp = int(raw_input())
    p.append((i, tmp))
    if not sum_p:
        sum_p.append(tmp)
    else:
        sum_p.append(sum_p[-1] + tmp)
p.sort(key=lambda a: a[1])
pp = [each[1] for each in p]
cost += sum(pp)
for j in xrange(H):
    new = int(raw_input())
    cost += new
    minus = bisect.bisect_right(pp, new)
    cost += (W-minus) * new
    cost += sum_p[minus-1] if minus > 0 else 0

print cost

Submission status: Wrong Answer

Solution code:

def cost(x, y, a):
    if x[0] == y[0] and abs(x[1]-y[1])==1:
        if x[1] > y[1]:
            return a[1][y[i]]
        else:
            return a[1][x[i]]
    elif x[1] == y[1] and abs(x[0]-y[0])==1:
        if x[0] > y[0]:
            return a[0][y[i]]
        else:
            return a[0][x[i]]

W = 2 
H = 2

a = [[0 for i in range(W)] for j in range(H)]

for i in range(W):
    for j in range(H):
        a[i][j] = 1#input()

a = [[3,5], [2,7]]


print(29)

Submission status: Wrong Answer

Solution code:
w, h = map(int, input().split())

w += 1
h += 1

mst = [[-1 for y in range(h)] for x in range(w)]

edges = []

for x in range(w-1):
    p = int(input())
    for y in range(h):
        edges.append((p, (x, y), (x+1, y)))

for y in range(h-1):
    p = int(input())
    for x in range(w):
        edges.append((p, (x, y), (x, y+1)))

edges.sort()

print(mst)
print(edges)

groups = 0
mst_cost = 0

for edge in edges:
    if mst[edge[1][0]][edge[1][1]] == -1 and mst[edge[2][0]][edge[2][1]] == -1:
        #neither vertex is yet in the mst, add to a new group
        mst[edge[1][0]][edge[1][1]] = groups
        mst[edge[2][0]][edge[2][1]] = groups
        groups += 1
    elif mst[edge[1][0]][edge[1][1]] != -1 and mst[edge[2][0]][edge[2][1]] == -1:
        # first vertex is in the mst, add second vertex to group
        mst[edge[2][0]][edge[2][1]] = mst[edge[1][0]][edge[1][1]]
    elif mst[edge[1][0]][edge[1][1]] != -1 and mst[edge[2][0]][edge[2][1]] == -1:
        # second vertex is in the mst, add first vertex to group
        mst[edge[1][0]][edge[1][1]] = mst[edge[2][0]][edge[2][1]]
    else:
        # both verticies are in mst
        if mst[edge[1][0]][edge[1][1]] == mst[edge[2][0]][edge[2][1]]:
            # if they're in the same group do nothing
            continue
        else:
            # if they're in different groups, merge groups
            new_group = mst[edge[2][0]][edge[2][1]]
            old_group = mst[edge[1][0]][edge[1][1]]
            for x in range(w):
                for y in range(h):
                    if mst[x][y] == old_group:
                        mst[x][y] = new_group

    print(mst)
    mst_cost += edge[0]

print(mst_cost)

Submission status: Wrong Answer

Solution code:
W, H = map(int, raw_input().split())
p = sorted([(int(raw_input()), 'p') for w in xrange(W)])
q = sorted([(int(raw_input()), 'q') for h in xrange(H)])

ans = 0
w, h = W+1, H+1
before = ''
costs = sorted(p+q)
for i in xrange(len(costs)):
    c, idx = costs[i]
    #print ans, w, h, c                                                                                                                                       
    if idx == 'p':
        if before != '' and before != idx:
            w = h = min(w-1, h-1)
        ans += c*h
    else:
        if before != '' and before != idx:
            w = h = min(h-1, w-1)
        ans += c*w
    before = idx
print ans

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph, flag):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    if flag:
        phc = ph[1:][:]
        phc.sort()
    
        phs = [0]
        for i in range(len(phc)):
            phs.append(phs[-1] + phc[i])
    
        for i in range(1, w):
            index = bisect.bisect_left(phc, pw[i])
            cost += phs[index] + pw[i] * (len(phc) - index)
    else:
        pwc = pw[1:][:]
        pwc.sort()
    
        pws = [0]
        for i in range(len(pwc)):
            pws.append(pws[-1] + pwc[i])
    
        for i in range(1, h):
            index = bisect.bisect_left(pwc, ph[i])
            cost += pws[index] + ph[i] * (len(pwc) - index)

    return cost

cost = 10 ** 50

'''
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))
'''

pw.sort()
ph.sort()

cost = min(cost, test(pw, ph, True))
cost = min(cost, test(pw[::-1], ph, True))
cost = min(cost, test(pw, ph[::-1], True))
cost = min(cost, test(pw[::-1], ph[::-1], True))

cost = min(cost, test(pw, ph, False))
cost = min(cost, test(pw[::-1], ph, False))
cost = min(cost, test(pw, ph[::-1], False))
cost = min(cost, test(pw[::-1], ph[::-1], False))

print cost

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = 10 ** 50

'''
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))
'''

pw.sort()
ph.sort()

cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))

print cost

Submission status: Wrong Answer

Solution code:
x = raw_input()

w,h = [int(i) for i in x.split()]

p = []
for i in range(w):
    p.append(input())

q = []
for i in range(h):
    q.append(input())


cost = 0

p.sort()
q.sort()

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = 10 ** 30
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))

pw.sort()
ph.sort()

cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))

print cost

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = 10 ** 30
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))

pwmi = pw.index(min(pw))
pwma = pw.index(max(pw))
phmi = ph.index(min(ph))
phma = ph.index(max(ph))
cost = min(cost, test(pw[pwmi:] + pw[:pwmi], ph[phmi:] + ph[:phmi]))
cost = min(cost, test(pw[pwmi:] + pw[:pwmi], ph[phma:] + ph[:phma]))
cost = min(cost, test(pw[pwma:] + pw[:pwma], ph[phmi:] + ph[:phmi]))
cost = min(cost, test(pw[pwma:] + pw[:pwma], ph[phma:] + ph[:phma]))

cost = min(cost, test(sorted(pw), sorted(ph)))
cost = min(cost, test(sorted(pw, reverse = True), sorted(ph)))
cost = min(cost, test(sorted(pw), sorted(ph, reverse = True)))
cost = min(cost, test(sorted(pw, reverse = True), sorted(ph, reverse = True)))

print cost

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = 10 ** 30
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))

pwmi = pw.index(min(pw))
pwma = pw.index(max(pw))
phmi = ph.index(min(ph))
phma = ph.index(max(ph))
cost = min(cost, test(pw[pwmi:] + pw[:pwmi], ph[phmi:] + ph[:phmi]))
cost = min(cost, test(pw[pwmi:] + pw[:pwmi], ph[phma:] + ph[:phma]))
cost = min(cost, test(pw[pwma:] + pw[:pwma], ph[phmi:] + ph[:phmi]))
cost = min(cost, test(pw[pwma:] + pw[:pwma], ph[phma:] + ph[:phma]))
print cost

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = 10 ** 30
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))

pwm = pw.index(min(pw))
phm = ph.index(min(ph))
cost = min(cost, test(pw[pwm:] + pw[:pwm], ph[phm:] + ph[:phm]))
print cost

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = 10 ** 30
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))
print cost

Submission status: Wrong Answer

Solution code:
import sys
import bisect

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
 
    phc = ph[1:][:]
    phc.sort()

    phs = [0]
    for i in range(len(phc)):
        phs.append(phs[-1] + phc[i])

    for i in range(1, w):
        index = bisect.bisect_left(phc, pw[i])
        cost += phs[index] + pw[i] * (len(phc) - index)

    return cost

cost = sys.maxint
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))
print cost

Submission status: Wrong Answer

Solution code:
import sys

w, h = map(int, raw_input().split())

pw = []
for i in range(w):
    pw.append(int(raw_input()))

ph = []
for i in range(h):
    ph.append(int(raw_input()))

def test(pw, ph):
    cost = (pw[0] + ph[0]) * 2 - max(pw[0], ph[0])
    
    for i in range(1, w):
        cost += pw[i] + ph[0]
    
    for i in range(1, h):
        cost += ph[i] + pw[0]
    
    for i in range(1, w):
        for j in range(1, h):
            cost += min(pw[i], ph[j])

    return cost

cost = sys.maxint
cost = min(cost, test(pw, ph))
cost = min(cost, test(pw[::-1], ph))
cost = min(cost, test(pw, ph[::-1]))
cost = min(cost, test(pw[::-1], ph[::-1]))
print cost

Submission status: Time Limit Exceeded

Solution code:
W,H=[int(item) for item in input().split()]
p=[]
for _ in range(W):
    p.append(int(input()))

q=[]
for _ in range(H):
    q.append(int(input()))

#cost = [[114514] * (W+1) for i in range(H+1)]
#cost[0][0]=0
cnt = 1
totalcost=0
while True:
    if cnt <= H :
        x,y=0,cnt
    else:
        x,y=cnt-H,H
        if cnt-H==W+1:break
    while y>=0 and x<=W:
        if x == 0:
            #cost[x][y]=cost[x][y-1]+q[y-1]
            totalcost+=q[y-1]
        elif y == 0:
            #cost[x][y]=cost[x-1][y]+p[x-1]
            totalcost+=p[x-1]
        else:
            totalcost += p[x - 1] if p[x - 1] < q[y - 1] else q[y-1]
            # if cost[x][y - 1] + q[y - 1] < cost[x - 1][y] + p[x - 1]:
            #    cost[x][y]=cost[x][y-1]+q[y-1]
            #    totalcost+=q[y-1]
            # else:
            #    cost[x][y]=cost[x-1][y]+p[x-1]
            #    totalcost += p[x - 1]
        #print(x,y)
        x += 1
        y -= 1
    #print(cnt)
    #print(cost)
    cnt += 1
print(totalcost)

Submission status: Time Limit Exceeded

Solution code:
import heapq
w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]
que = [(0, 0, 0)]
t, y, x = 0, 0, 0
seen = [[False]*(w+1) for _ in range(h+1)]
ans = 0
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
for _ in range((w+1)*(h+1)):
  while seen[y][x]:
    t, y, x = heapq.heappop(que)
  seen[y][x] = True
  ans += t
  for i in range(4):
    ny = y+dy[i]
    nx = x+dx[i]
    if 0<=ny<=h and 0<=nx<=w:
      if seen[ny][nx]:
        continue
      if dy[i]==0:
        heapq.heappush(que, (P[min(x, nx)], ny, nx))
      else:
        heapq.heappush(que, (Q[min(y, ny)], ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(W, H, P, Q):
    W += 1
    H += 1
    ans = 0
    for i, p in enumerate(P):
        ans += p

    for i, q in enumerate(Q):
        ans += q


    for i in range(1, H):
        for j in range(1, W):
            if P[j-1] < Q[i-1]:
                ans += P[j-1]
            else:
                ans += Q[i-1]

    return ans


def main():
    W, H = read_int_n()
    P = [read_int() for _ in range(W)]
    Q = [read_int() for _ in range(H)]
    print(slv(W, H, P, Q))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
W,H = map(int,input().split())
P = [int(input()) for _ in range(W)]
Q = [int(input()) for _ in range(H)]
heap = [[0,(0,0)]]
hist = {(i,j):0 for i in range(W+1) for j in range(H+1)}
cnt = 0
while heap:
    x = heapq.heappop(heap)
    i,j = x[1][0],x[1][1]
    if hist[(i,j)]==1:continue
    hist[(i,j)] = 1
    cnt += x[0]
    if i+1<=W and hist[(i+1,j)]==0:
        heapq.heappush(heap,[P[i],(i+1,j)])
    if j+1<=H and hist[(i,j+1)]==0:
        heapq.heappush(heap,[Q[j],(i,j+1)])
    if i-1>=0 and hist[(i-1,j)]==0:
        heapq.heappush(heap,[P[i-1],(i-1,j)])
    if j-1>=0 and hist[(i,j-1)]==0:
        heapq.heappush(heap,[Q[j-1],(i,j-1)])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


H, W = list(map(int, sys.stdin.readline().split()))
P = [int(sys.stdin.readline()) for _ in range(W)]
Q = [int(sys.stdin.readline()) for _ in range(H)]


def test():
    edges = []
    vs = []
    for h, w in itertools.product(range(H + 1), range(W + 1)):
        if w < W:
            edges.append((P[w], (w, h), (w + 1, h)))
        if h < H:
            edges.append((Q[h], (w, h), (w, h + 1)))
    for h, w in itertools.product(range(H + 1), range(W + 1)):
        vs.append((w, h))
    edges.sort()

    # kruskal
    uf = UnionFind(nodes=vs)
    ret = 0
    for s, v, u in edges:
        if uf.root(v) != uf.root(u):
            uf.unite(v, u)
            ret += s
    return ret


# 横棒
hs = []
for w in range(W):
    hs.append((P[w], w, w + 1))
# 縦棒
vs = []
for h in range(H):
    vs.append((Q[h], h, h + 1))

hs.sort(reverse=True)
vs.sort(reverse=True)

ans = 0
v_nodes = W + 1
h_nodes = H + 1
while hs or vs:
    if not vs or (hs and hs[-1] < vs[-1]):
        # 横棒を使う
        s, i, j = hs.pop()
        # まだくっつけてない横軸の数だけ辺を張る
        ans += s * h_nodes
        v_nodes -= 1
    else:
        # 縦棒のが短い
        s, i, j = vs.pop()
        ans += s * v_nodes
        h_nodes -= 1
# print(ans)

print(test())

Submission status: Time Limit Exceeded

Solution code:
W,H = map(int,input().split())

side = []
for i in range(W):
    side.append({"cost":int(input()),"num":i,"dir":0})
for i in range(H):
    side.append({"cost":int(input()),"num":i,"dir":1})
side = sorted(side,key = lambda x:x["cost"])

node =[[{"v":j,"men":[j]} for j in range(i*(W+1),(i+1)*(W+1))]for i in range(H+1)]
ans = 0
for s in side:
    cost,num,di = s["cost"],s["num"],s["dir"]
    if di == 0 :
        for i in range(H+1):
            if node[i][num]["v"] != node[i][num+1]["v"]: # 親が違ったら
                # print(i,num,0)
                ans += cost
                v1 = node[i][num]["v"]
                v2 = node[i][num+1]["v"]
                
                for j in node[v2//(W+1)][v2%(W+1)]["men"]: # v2とつながった要素の親を書き換え
                    node[j//(W+1)][j%(W+1)]["v"] = v1
                node[v1//(W+1)][v1%(W+1)]["men"] += node[v2//(W+1)][v2%(W+1)]["men"]
    else:
        for i in range(W+1):
            if node[num][i]["v"] != node[num+1][i]["v"]: # 親が違ったら
                # print(num,i,1)
                ans += cost
                v1 = node[num][i]["v"]
                v2 = node[num+1][i]["v"]
                
                for j in node[v2//(W+1)][v2%(W+1)]["men"]: # v2とつながった要素の親を書き換え
                    node[j//(W+1)][j%(W+1)]["v"] = v1
                node[v1//(W+1)][v1%(W+1)]["men"] += node[v2//(W+1)][v2%(W+1)]["men"]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

W,H=map(int,input().split())
p=[int(input()) for _ in range(W)]
q=[int(input()) for _ in range(H)]
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W):
  for j in range(H):
    ans-=max(p[i],q[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
W,H=map(int,input().split())
p=[]
q=[]
for i in range(W):
  p.append(int(input()))
for i in range(H):
  q.append(int(input()))
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W):
  for j in range(H):
    ans-=max(p[i],q[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
W,H = map(int,input().split())
PQ = [(int(input()),0,i) for i in range(W)] + [(int(input()),1,i) for i in range(H)]
PQ.sort()

import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self):
        self.Parent = {}
    def add(self,k):
        self.Parent[k] = k
    def get_Parent(self,n):
        if self.Parent[n] == n:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

ans = 0
T = UnionFind()
for i in range(W+1):
    for j in range(H+1):
        T.add((i,j))
for c,pq,ij in PQ:
    if pq==0:
        i = ij
        for j in range(H+1):
            if not T.is_united((i,j),(i+1,j)):
                T.merge((i,j),(i+1,j))
                ans += c
    else:
        j = ij
        for i in range(W+1):
            if not T.is_united((i,j),(i,j+1)):
                T.merge((i,j),(i,j+1))
                ans += c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
W,H=map(int,raw_input().split())
p=[input() for i in range(W)]
q=[input() for i in range(H)]

p.sort(reverse=True)
q.sort(reverse=True)

cost=0
del_H=0
del_W=0
len_p=W
len_q=H

while 1:

    try:
        if p[0]>q[0]:
            del_W+=1
            cost+=p[0]*(del_H+1)
            del p[0]
            len_p-=1
        else:
            del_H+=1
            cost+=q[0]*(del_W+1)
            del q[0]
            len_q-=1

    except:
        break

    
if len_p==0:
    cost+=sum(q)*(W+1)

else:
    cost+=sum(p)*(H+1)

print cost