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: 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 len_p>0 and len_q>0:
    
    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
        

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

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

print cost

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
#from networkx import nx
import sys

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(dict)
    def add_edge(self, x, y, weight):
        self.graph[x][y] = weight
    def __getitem__(self, x):
        return self.graph[x]
    def __str__(self):
        return str(self.graph)

def build_graph(W, H, p, q):
    graph = Graph()
    for i in range(W):
        for j in range(H):
            x = j*W + i
            if i+1 < W:
                graph.add_edge(x, x+1, p[i])
                graph.add_edge(x+1, x, p[i])
            if j+1 < H:
                graph.add_edge(x, x+W, q[j])
                graph.add_edge(x+W, x, q[j])
    return graph

def prim(G, s):
    P, Q = {}, [(0, None, s)]   
    while Q:
        _, p, u = heappop(Q)
        if u in P: 
            continue
        P[u] = p
        for v, w in G[u].items():
            heappush(Q, (w, u, v))
    return sum(G[x][y] for x,y in P.items() if y != None)

W, H = map(int, raw_input().split(' '))
p = [0] * W
q = [0] * H
for i in xrange(W):
    p[i] = int(raw_input())
for j in xrange(H):
    q[j] = int(raw_input())
W+=1
H+=1
g = build_graph(W, H, p, q)
p = prim(g, 0)
print p

Submission status: Time Limit Exceeded

Solution code:
import sys

def build_graph(W, H, p, q):
    vetex = W * H
    graph = [[sys.maxint]*vetex for _ in range(vetex)]
    for i in range(W):
        for j in range(H):
            x = j*W + i
            if i+1 < W:
                graph[x][x+1] = p[i]
            if j+1 < H:
                graph[x][x+W] = q[j]
    return graph
def prim(graph,n):  
    dis=[0]*n  
    pre=[0]*n  
    flag=[False]*n  
    flag[0]=True  
    k=0  
    for i in range(n):  
        dis[i]=graph[k][i]  
    for j in range(n-1):  
        mini=sys.maxint  
        for i in range(n):  
            if mini>dis[i] and not flag[i]:  
                mini=dis[i]  
                k=i  
        if k==0: 
            return  
        flag[k]=True  
        for i in range(n):  
            if dis[i]>graph[k][i] and not flag[i]:  
                dis[i]=graph[k][i]  
                pre[i]=k  
    return dis,pre

W, H = map(int, raw_input().split(' '))
p = [0] * W
q = [0] * H
for i in xrange(W):
    p[i] = int(raw_input())
for j in xrange(H):
    q[j] = int(raw_input())
W+=1
H+=1
g = build_graph(W, H, p, q)
dis, pre = prim(g, W*H)
print sum(dis[1:])

Submission status: Time Limit Exceeded

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

p_list = list()
q_list = list()

for i in range(W):
    p_list.append(int(raw_input()))
    
for j in range(H):
    q_list.append(int(raw_input()))

p_list.sort()
q_list.sort()

cp = H+1
cq = W+1

res = 0

while len(p_list) + len(q_list) > 0:
    if len(p_list) == 0:
        choice = 'q'
    elif len(q_list) == 0:
        choice = 'p'
    elif p_list[0] < q_list[0]:
        choice = 'p'
    else:
        choice = 'q'
    if choice == 'p':
        cq -= 1
        res += cp*p_list.pop(0)
    else:
        cp -= 1
        res += cq*q_list.pop(0)

print res

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *
from array import *

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def mst_prim(adj, n):
    pred = defaultdict(lambda: -1)
    key = defaultdict(lambda: float('inf'))
    key[0] = 0
    pq = [(key[v], v) for v in range(n)]
    heapify(pq)
    in_pq = array('B', (True for _ in range(n)))
    while pq:
        _,u = heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

def main():
    w, h = reads()
    p = [read() for _ in range(w)]
    q = [read() for _ in range(h)]

    adj = defaultdict(set)
    for x in range(w+1):
        for y in range(h+1):
            if x < w:
                adj[x+y*(w+1)].add((x+1+y*(w+1), p[x]))
                adj[x+1+y*(w+1)].add((x+y*(w+1), p[x]))
            if y < h:
                adj[x+y*(w+1)].add((x+(y+1)*(w+1), q[y]))
                adj[x+(y+1)*(w+1)].add((x+y*(w+1), q[y]))
    print(sum(mst_prim(adj, (w+1)*(h+1))[1].values()))

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

class DisjointSet:
    def __init__ (self, size):
        self.parent = [0] * size
        self.rank =   [0] * size
        for i in xrange(size):
            self.parent[i] = i

    def union(self, x, y):
        self.link( self.find_set(x), self.find_set(y) )
            
    def link (self, x, y):
        if self.rank[x] > self.rank[y]:
            self.parent[y] = self.parent[x]
        else:
            self.parent[x] = self.parent[y]
            if (self.rank[x] == self.rank[y]):
                self.rank[x] += self.rank[y] + 1

    def find_set (self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        return self.parent[x]

class Edge:
    def __init__(self, src, dst, weight):
        self.src   = src
        self.dst   = dst
        self.weight = weight

edges = []
W,H=map(int,raw_input().split())
for i in range(W):
    p=input()
    for j in range(H+1):
        h1=str(i)+str(j)
        h2=str(i+1)+str(j)
        edges.append(Edge(h1,h2,p))
for j in range(H):
    q=input()
    for i in range(W+1):
        h1=str(i)+str(j)
        h2=str(i)+str(j+1)
        edges.append(Edge(h1,h2,q))
c2i={}
cnt=0
for i in range(W+1):
    for j in range(H+1):
        h=str(i)+str(j)
        c2i[h]=cnt
        cnt+=1
set = DisjointSet((W+1)*(H+1)) # the number of vertices
mst = []

edges.sort(lambda x, y: x.weight - y.weight )
for x in edges:
    u = c2i[x.src]
    v = c2i[x.dst]
    if set.find_set(u) != set.find_set(v):
        mst.append(x)
        set.union(u, v)

print sum(map(lambda x: x.weight, mst))

Submission status: Time Limit Exceeded

Solution code:
import bisect
cost = 0
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append((i, int(raw_input())))
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
    for k in xrange(minus):
        cost += pp[k]

print cost

Submission status: Time Limit Exceeded

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()

groups = 0
mst_cost = 0
edges_placed = 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

    mst_cost += edge[0]
    edges_placed += 1
    if edges_placed == w*h:
        break

print(mst_cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __repr__(self):
        return '({},{})'.format(self.x, self.y)

def dist(p1, p2, p, q):
    if (p1.x,p1.y) == (p2.x, p2.y):
        return float('inf')
    if p1.x == p2.x and abs(p1.y - p2.y) == 1:
        return q[min(p1.y, p2.y)]
    elif p1.y == p2.y and abs(p1.x - p2.x) == 1:
        return p[min(p1.x, p2.x)]
    return float('inf')

def mst(ps, p, q):
    m =  [[dist(ps[i], ps[j], p, q) for i in range(len(ps))] for j in range(len(ps))]

    X = set([0])
    Y = set(range(len(ps))[1:])
    cost = 0
    edges = []
    while len(Y) != 0:
        mcost = float('inf')
        edge = None
        for ex in X:
            for ey in Y:
                if mcost > m[ex][ey]:
                    mcost = m[ex][ey]
                    edge = [ex, ey]
        X.add(edge[1])
        Y.remove(edge[1])

        cost += mcost
        edges.append(edge)
    return cost, edges

def main():
    w, h = reads()
    p = [read() for _ in range(w)]
    q = [read() for _ in range(h)]
    points = []
    for x in range(w+1):
        for y in range(h+1):
            points.append((Point(x,y)))
    print(int(mst(points, p, q)[0]))

main()

Submission status: Time Limit Exceeded

Solution code:
w, h = map(int, raw_input().split())
ps = [input() for i in range(w)]
qs = [input() for i in range(h)]

queue = {(1, 0): ps[0], (0, 1): qs[0]}

ret = 0

while queue:
    cand = {e[0]: sum(e[0]) for e in queue.items()
            if e[1] == min(queue.values())}
    now = min(cand.items(), key=lambda x: x[1])[0]
    ret += queue[now]
    if now[0] < w and (now[0] + 1, now[1]):
        queue[(now[0] + 1, now[1])] = ps[now[0]]
    if now[1] < h and (now[0], now[1] + 1):
        queue[(now[0], now[1] + 1)] = qs[now[1]]
    del queue[now]

print ret

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


class UnionFind(object):
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def same(self, x, y):
        return self.find(x) == self.find(y)
        
    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
    
    def union_bad(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] > self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

w,h = map(int, input().split(' '))
p = []
for i in range(w):
    p.append(int(input()))
q = []
for i in range(h):
    q.append(int(input()))

p = np.array(p)
q = np.array(q)
p = np.concatenate((p,q))
s_i_p = np.argsort(p)

uf = UnionFind((w+1)*(h+1))
res = 0
p_i = 0
i = 0
while i < 2*w*h+w+h:
    j = 0
    while j < (h+1 if s_i_p[p_i] < w else w+1):
        c= p[s_i_p[p_i]]
        if s_i_p[p_i] < w:
            x = s_i_p[p_i]
            y = j
            v = x + y*(w+1)
            u = v + 1
        else:
            x = j
            y = s_i_p[p_i]-w
            v = x + y*(w+1)
            u = v + w +1
        if uf.same(u,v) == False:
            uf.union(u,v)
            res += c
        j+=1
        i+=1
    p_i += 1
    
print(res)

Submission status: Time Limit Exceeded

Solution code:
w,h= map(int, raw_input().split())
p =[]
q = []
for i in xrange(w):
    t = input()
    p.append(t)

for i in xrange(h):
    t = input()
    q.append(t)
p =sorted(p,reverse=True)
q =sorted(q, reverse=True)
ac = p[:]
i = w-2
while i >=0:
    ac[i] += ac[i+1]
    i -=1
c = ac[0] + sum(q)
for i in xrange(h):
    for j in xrange(w):
        if q[i] > p[j]:
            c += ac[j]
            break
        c += q[i]
print c

Submission status: Time Limit Exceeded

Solution code:
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append(int(raw_input()))
for j in xrange(H):
    q.append(int(raw_input()))

cost = 0
for i in xrange(W+1):
    for j in xrange(H+1):
        if i == 0 and j == 0: continue
        cost += min(p[i-1] if i > 0 else 100000005, q[j-1] if j > 0 else 100000005)
print cost

Submission status: Time Limit Exceeded

Solution code:
t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append(int(raw_input()))
for j in xrange(H):
    q.append(int(raw_input()))

node = [
    (i, j, min(p[i-1] if i > 0 else 100000005, q[j-1] if j > 0 else 100000005)) for i in xrange(W+1) for j in xrange(H+1)
]
cost = 0
for i in xrange(W*H+W+H):
    cost += node[i+1][2]
print cost

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
W,H = map(int,input().split())
Ps = []
Qs = []
for w in range(W):
    Ps.append(int(input()))
for h in range(H):
    Qs.append(int(input()))


def func(p_min, p_max, q_min, q_max):
    # print("func({},{},{},{})".format(p_min, p_max, q_min, q_max))

    if p_min == p_max and q_min == q_max:
        return 0
    if p_min == p_max:
        # print("ver")
        return sum(Qs[q_min:q_max])
    if q_min == q_max:
        # print("hor")
        return sum(Ps[p_min:p_max])

    max_p = max(Ps[p_min:p_max])
    max_q = max(Qs[q_min:q_max])

    if max_p < max_q:
        max_q_idx = Qs[q_min:q_max].index(max_q) + q_min
        ans1 = func(p_min, p_max, q_min, max_q_idx)
        ans2 = func(p_min, p_max, max_q_idx + 1, q_max)
        return ans1 + ans2 + max_q
    else:
        max_p_idx = Ps[p_min:p_max].index(max_p) + p_min
        ans1 = func(p_min, max_p_idx, q_min, q_max)
        ans2 = func(max_p_idx + 1, p_max, q_min, q_max)
        return ans1 + ans2 + max_p

print(func(0, W, 0, H))

Submission status: Time Limit Exceeded

Solution code:
w, h = map(int, raw_input().split())
p = []
q = []
for i in range(w):
    p.append(int(raw_input()))
for i in range(h):
    q.append(int(raw_input()))

wl = w
hl = h

cost = 0

p.sort()
q.sort()

p.append(10 ** 8 + 1)
q.append(10 ** 8 + 1)

while(wl + hl > 0):
    if p[0] < q[0]:
        cost += (hl + 1) * p[0]
        p.pop(0)
        wl -= 1
    else:
        cost += (wl + 1) * q[0]
        q.pop(0)
        hl -= 1

print cost

Submission status: Time Limit Exceeded

Solution code:
w, h = map(int, raw_input().split())
ps = [input() for i in range(w)]
qs = [input() for i in range(h)]

queue = {(1, 0): ps[0], (0, 1): qs[0]}
visited = [(0, 0)]

ret = 0

while queue:
    now_cost = min(queue.items(), key=lambda x: x[1])[1]
    cand = {e[0]: sum(e[0]) for e in queue.items() if e[1] == now_cost}
    now = min(cand.items(), key=lambda x: x[1])[0]
    # now = min(queue.items(), key=lambda x: x[1])[0]
    # print "visited", visited
    # print "queue", queue
    # print "now", now, queue[now]
    ret += queue[now]
    if now not in visited:
        visited.append(now)
    # if now[0] > 0 and (now[0] + 1, now[1]) not in visited:
    #     queue[(now[0] - 1, now[1])] = ps[now[0] - 1]
    # if now[1] > 0 and (now[0], now[1] + 1) not in visited:
    #     queue[(now[0], now[1] - 1)] = qs[now[1] - 1]
    if now[0] < w and (now[0] + 1, now[1]) not in visited:
        queue[(now[0] + 1, now[1])] = ps[now[0]]
    if now[1] < h and (now[0], now[1] + 1) not in visited:
        queue[(now[0], now[1] + 1)] = qs[now[1]]
    del queue[now]

print ret

Submission status: Time Limit Exceeded

Solution code:
import sys
W,H = map(int, sys.stdin.readline().strip().split())
p = []
q = []
ds = []
def union(a,b):
    i=0
    while i< len(ds):
        if ds[i] == b:
            ds[i] = a
        i+=1
def setId(i,j):
    return ds[i*(W+1)+j]
def linkx(t):
    j = t[0]
    c = t[1]
    retc = 0
    rete = 0
    for i in xrange(H+1):
        if setId(i, j) != setId(i, j+1):
            retc +=c
            rete +=1
            union(setId(i,j), setId(i,j+1))
    return rete,retc
def linky(t):
    i = t[0]
    c = t[1]
    retc = 0
    rete = 0
    for j in xrange(W+1):
        if setId(i, j) != setId(i+1, j):
            retc +=c
            rete +=1
            union(setId(i,j), setId(i+1,j))
    return rete,retc
for i in xrange(W):
    p.append( (i,int(sys.stdin.readline().strip())) )
p = sorted( p, key=lambda x:x[1] )
for i in xrange(H):
    q.append( (i,int(sys.stdin.readline().strip())) )
q = sorted( q, key=lambda x:x[1] )

for i in xrange(H+1):
    for j in xrange(W+1):
        ds.append(i*(W+1) + j)

edgeCount = 0
edgeTotal = (W+1)*(H+1) -1
costTotal = 0
while edgeCount != edgeTotal:
    if p and q:

        if p[0][1] < q[0][1]:
            edge,cost = linkx(p.pop(0))
        else:
            edge,cost = linky(q.pop(0))
        edgeCount += edge
        costTotal += cost
        continue
    if p :
        edge,cost = linkx(p.pop(0))
        edgeCount += edge
        costTotal += cost
        continue
    if q :
        edge,cost = linky(q.pop(0))
        edgeCount += edge
        costTotal += cost
        continue

print costTotal

Submission status: Time Limit Exceeded

Solution code:
w, h = map(int, raw_input().split())
p = []
q = []
for i in range(w):
    p.append(int(raw_input()))
for i in range(h):
    q.append(int(raw_input()))

wl = w
hl = h

cost = 0

while(wl + hl > 0):
    if len(p) > 0:
        mp = min(p)
    else:
        mp = 10 ** 8 + 1
    if len(q) > 0:
        mq = min(q)
    else:
        mq = 10 ** 8 + 1
    if mp < mq:
        cost += (hl + 1) * mp
        p.pop(p.index(mp))
        wl -= 1
    else:
        cost += (wl + 1) * mq
        q.pop(q.index(mq))
        hl -= 1

print cost

Submission status: Time Limit Exceeded

Solution code:
W, H = map(int, raw_input().split())
p = sorted([(i, int(raw_input())) for i in xrange(W)], key=lambda x:-x[1])
q = sorted([(i, int(raw_input())) for i in xrange(H)], key=lambda x:-x[1])

class UnionFind(object):
    def __init__(self, n):
        self.uf = [-1 for _ in xrange(n)]

    def union(self, x, y):
        x = self.find(x[0] + x[1]*(W+1))
        y = self.find(y[0] + y[1]*(W+1))
        if x == y:
            return False
        if self.uf[x] >= self.uf[y]:
            self.uf[y] += self.uf[x]
            self.uf[x] = y
        else:
            self.uf[x] += self.uf[y]
            self.uf[y] = x
        return True

    def find(self, x):
        leaves = []
        while self.uf[x] >= 0:
            leaves.append(x)
            x = self.uf[x]
        for lf in leaves:
            self.uf[lf] = x
        return x

uf = UnionFind((W+1)*(H+1))
ans = 0
while len(p) > 0 or len(q) > 0:
    if len(q) == 0 or (len(p) > 0 and p[-1][1] <= q[-1][1]):
        i, cost = p.pop()
        for j in xrange(H+1):
            if uf.union((i, j), (i+1, j)):
                ans += cost
    else:
        j, cost = q.pop()
        for i in xrange(W+1):
            if uf.union((i, j), (i, j+1)):
                ans += cost
print ans

Submission status: Time Limit Exceeded

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()

iter = w+h


for i in range(iter):

    if(w==0):
        cost += q[0]*(w+1)
        h -= 0
        q.pop(0)

    elif(h==0):
        cost += p[0]*(h+1)
        w -= 0
        p.pop(0)

    elif(p[0]==q[0] and h>w):
        cost += p[0]*(h+1)
#        print cost,w,h
        w -= 1
        p.pop(0)

    elif(p[0]<q[0]):
        cost += p[0]*(h+1)
 #       print cost,w,h
        w -= 1
        p.pop(0)
    
    else:
        cost += q[0]*(w+1)
  #      print cost,w,h
        h -= 1
        q.pop(0)
    

print cost

Submission status: Time Limit Exceeded

Solution code:
neighbor = lambda c, w, h: filter(
    lambda b: 0 <= b[0] <= w and 0 <= b[1] <= h,
    [
        (c[0]-1, c[1]),
        (c[0]+1, c[1]),
        (c[0], c[1]-1),
        (c[0], c[1]+1)
    ]
)

t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append(int(raw_input()))
for j in xrange(H):
    q.append(int(raw_input()))

has = [[False for i in xrange(H+1)] for j in xrange(W+1)]
has[0][0] = True
Next = [(1, 0), (0, 1)]

cost = 0
for i in xrange(W*H+W+H):
    Min = 100000005
    choose = None
    Next.sort(key=lambda a: min(p[a[0]-1] if a[0] > 0 else 100000005, q[a[1]-1] if a[1] > 0 else 100000005))
    choose = Next[-1]
    Min = min(p[choose[0]-1] if choose[0] > 0 else 100000005, q[choose[1]-1] if choose[1] > 0 else 100000005)
    # for each in Next:
    #     if each[0] > 0:
    #         if p[each[0]-1] < Min:
    #             choose = each
    #             Min = p[each[0]-1]
    #     if each[1] > 0:
    #         if q[each[1]-1] < Min:
    #             choose = each
    #             Min = q[each[1]-1]
    has[choose[0]][choose[1]] = True
    Next = Next[:-1]
    cost += Min
    for every in neighbor(choose, W, H):
        # print every
        if not has[every[0]][every[1]] and every not in Next:
            Next.append(every)
print cost

Submission status: Time Limit Exceeded

Solution code:
w,h= map(int, raw_input().split())
p =[]
q = []
for i in xrange(w):
    t = input()
    p.append(t)

for i in xrange(h):
    t = input()
    q.append(t)
c = sum(p) + sum(q)
for i in xrange(h):
    for j in xrange(w):
        c += min(p[j], q[i])
print c

Submission status: Time Limit Exceeded

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


iter = w+h


for i in range(iter):

    if(len(p)==0):
        cost += min(q)*(w+1)
        h -= 0
        q.remove(min(q))

    elif(len(q)==0):
        cost += min(p)*(h+1)
        w -= 0
        p.remove(min(p))

    elif(min(p)==min(q) and h>w):
        cost += min(p)*(h+1)
        w -= 1
        p.remove(min(p))

    elif(min(p)<min(q)):
        cost += min(p)*(h+1)
 #       print cost,w,h
        w -= 1
        p.remove(min(p))
    
    else:
        cost += min(q)*(w+1)
  #      print cost,w,h
        h -= 1
        q.remove(min(q))
    

print cost

Submission status: Time Limit Exceeded

Solution code:
"""UnionFind.py

Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.

Taken from https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py
"""

class UnionFind:
    """Union-find data structure.

    Each unionFind instance X maintains a family of disjoint sets of
    hashable objects, supporting the following two methods:

    - X[item] returns a name for the set containing the given item.
      Each set is named by an arbitrarily-chosen one of its members; as
      long as the set remains unchanged it will keep the same name. If
      the item is not yet part of a set in X, a new singleton set is
      created for it.

    - X.union(item1, item2, ...) merges the sets containing each item
      into a single larger set.  If any item is not yet part of a set
      in X, it is added to X as one of the members of the merged set.
    """

    def __init__(self):
        """Create a new empty union-find structure."""
        self.weights = {}
        self.parents = {}

    def __getitem__(self, object):
        """Find and return the name of the set containing the object."""

        # check for previously unknown object
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object

        # find path of objects leading to the root
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        """Iterate through all items ever found or unioned by this structure."""
        return iter(self.parents)

    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        heaviest = max([(self.weights[r],r) for r in roots])[1]
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

w, h = [int(x) for x in input().split()]
p = [int(input()) for _ in range(w)]
q = [int(input()) for _ in range(h)]

uf = UnionFind()
for i in range(w + 1):
    for j in range(h + 1):
        _ = uf[i, j]

edges = []
for i in range(w):
    for j in range(h + 1):
        edges.append((p[i], i, j, i + 1, j))
for i in range(w + 1):
    for j in range(h):
        edges.append((q[j], i, j, i, j + 1))
edges.sort()

ans = 0

for cost, x, y, x2, y2 in edges:
    if uf[x, y] != uf[x2, y2]:
        uf.union((x, y), (x2, y2))
        ans += cost

print(ans)

Submission status: Time Limit Exceeded

Solution code:
neighbor = lambda c, w, h: filter(
    lambda b: 0 <= b[0] <= w and 0 <= b[1] <= h,
    [
        (c[0]-1, c[1]),
        (c[0]+1, c[1]),
        (c[0], c[1]-1),
        (c[0], c[1]+1)
    ]
)

t = raw_input()
W, H = map(int, t.split(' '))
p, q = [], []
for i in xrange(W):
    p.append(int(raw_input()))
for j in xrange(H):
    q.append(int(raw_input()))

has = [[False for i in xrange(H+1)] for j in xrange(W+1)]
has[0][0] = True
Next = [(1, 0), (0, 1)]

cost = 0
for i in xrange(W*H+W+H):
    Min = 100000005
    choose = None
    for each in Next:
        if each[0] > 0:
            if p[each[0]-1] < Min:
                choose = each
                Min = p[each[0]-1]
        if each[1] > 0:
            if q[each[1]-1] < Min:
                choose = each
                Min = q[each[1]-1]
    has[choose[0]][choose[1]] = True
    Next.remove(choose)
    cost += Min
    for every in neighbor(choose, W, H):
        # print every
        if not has[every[0]][every[1]] and every not in Next:
            Next.append(every)
print cost

Submission status: Time Limit Exceeded

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()

iter = w+h


for i in range(iter):

    if(len(p)==0):
        cost += q[0]*(w+1)
        h -= 0
        q.pop(0)

    elif(len(q)==0):
        cost += p[0]*(h+1)
        w -= 0
        p.pop(0)

    elif(p[0]==q[0] and h>w):
        cost += p[0]*(h+1)
#        print cost,w,h
        w -= 1
        p.pop(0)

    elif(p[0]<q[0]):
        cost += p[0]*(h+1)
 #       print cost,w,h
        w -= 1
        p.pop(0)
    
    else:
        cost += q[0]*(w+1)
  #      print cost,w,h
        h -= 1
        q.pop(0)
    

print cost

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    W,H = LI()
    s = []
    for _ in range(W):
        s.append((NI(),0))
    for _ in range(H):
        s.append((NI(),1))
    s.sort()
    x = 0
    y = 0
    ans = 0
    for r,d in s:
        if d == 0:
            ans += (H - y + 1) * r
            x += 1
        else:
            ans += (W - x + 1) * r
            y += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 最小全域木（mininum spanning tree）の問題

# 頂点、辺どちらの数もO(WH)なので、木を求めるアルゴリズムを直接適用するのは不可能（TLE）。
# 計算の工夫で計算量を減らす。
# クラスカル法（コストの小さい順に、閉路ができないように辺を追加）を用いる。
# 縦向きの辺は、最初はW+1本全てを選択する。「それまで選択された横の辺（の組）」の数だけ減る。その数だけ横がひと繋がりになっているので。
# 横向きの辺は、最初はH+1本全てを選択する。「それまで選択された縦の辺（の組）」の数だけ減る。その数だけ縦がひと繋がりになっているので。
# 縦と横の長さを一緒にしてソートするにはどうする?
# - 縦と横を独立にソートして、どちらが小さいか管理しながら左から見る。尺取り的なやり方。
# - 縦横情報を入れて長さで一緒にソートする。 →こっちが簡単そう。

w, h = list(map(int, input().split()))

yoko = [(int(input()), 'yoko') for _ in range(w)]
tate = [(int(input()), 'tate') for _ in range(h)]

sorted_edge = sorted(yoko + tate, key=lambda x: x[0])

ans = 0
tate_num = 0
yoko_num = 0
for length, direction in sorted_edge:
    if direction == 'tate':
        ans += length * (w + 1 - yoko_num)
        tate_num += 1
    else:
        ans += length * (h + 1 - tate_num)
        yoko_num += 1

print(ans)