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 heapq import heapify, heappop, heappush
W,H = map(int,input().split())
p = []
for i in range(H):
  temp = int(input())
  p.append(temp)
q = []
for i in range(W):
  temp = int(input())
  q.append(temp)
#print(p,q)
ans = 0
visited = set([(0,0)])
v = (0,0)
R = []
heappush(R, (q[v[0]],(0,1))) #繋がっている道のコストと点
heappush(R, (p[v[1]],(1,0)))
dxdy = [(0,1),(0,-1),(1,0),(-1,0)]
#print(R)
while len(visited) < (W+1)*(H+1):
  cost,v = heappop(R)
  if v in visited: #訪問済みなら次の道
    continue
  ans += cost
  visited.add(v)
  #print(v,cost)
  for i in range(4):
    dx = dxdy[i][0]
    dy = dxdy[i][1]
    nxt = (v[0]+dx,v[1]+dy)
    if 0<=nxt[0]<=H and 0<=nxt[1]<=W and nxt not in visited:
      if nxt[0] == v[0]: #x軸が一緒。y側に道をはる。
        ncost = q[v[1]]
      else:
        ncost = p[v[0]]
      heappush(R,(ncost,nxt))
      #print(ncost,nxt,"push")
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq


w,h =readints()
p = [readint() for i in range(w)]
q = [readint() for i in range(h)]

heapq.heapify(p)
heapq.heapify(q)

edge = 0
cost = 0
used = [0,0]

while edge < (h+1)*(w+1)-1:
    print(edge,cost)
    if p and q:
        if p[0]<q[0]:
            flag = 1
        else:
            flag = 0
    elif p:
        flag = 1
    else:
        flag = 0
    if flag:
        x = heapq.heappop(p)
        edge += h+1-used[1]
        cost += x * (h+1-used[1])
        used[0] += 1
    else:
        x = heapq.heappop(q)
        edge += w+1-used[0]
        cost += x * (w+1-used[0])
        used[1] += 1

print(cost)

Submission status: Wrong Answer

Solution code:
import heapq
w,h= map(int,input().split())
p = [-1*int(input()) for _ in range(w)]
q = [-1*int(input()) for _ in range(h)]
total = sum(p)*(h+1) + sum(q)*(w+1)
total *= -1
heapq.heapify(p)
heapq.heapify(q)
hhp = heapq.heappop
c=0
gen=0
w+=1
h+=1
while True:
    if p[0]<=q[0]:
        if h>1:
            gen += -1*hhp(p)*(w-1)
            h-=1
        else:
            if w>1:
                gen += -1*hhp(q)*(h-1)
                w-=1
            else:break
    elif p[0]>q[0]:
        if w>1:
            gen += -1*hhp(q)*(h-1)
            w-=1
        else:
            if h>1:
                gen += -1*hhp(p)*(w-1)
                h-=1
            else:break
    if len(p)==0 or len(q)==0:break
print(total-gen)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

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

P = [int(input()) for _ in range(W)]
Q = [int(input()) for _ in range(H)]

P.sort()
Q.sort()

cum_p = [0] + list(accumulate(P))
cum_q = [0] + list(accumulate(Q))

res = 0

N = min(len(cum_p), len(cum_q))

for i in range(N):
    res += cum_p[-1 - i] + cum_q[-1 - i]

for i in range(N - 1):
    res += min(P[-1 - i], Q[-1 - i])
    
print(res)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
v = []
for i in range(w):
    x = int(input())
    v.append((x, 0))
for i in range(h):
    x = int(input())
    v.append((x, 1))
v.sort()
zero = h + 1
one = w + 1
ans = 0
for p in v:
    x, k = p
    if k == 0:
        ans += x * zero
        one -= 1
    else:
        ans += x * one
        zero -= 1
print(ans)

Submission status: Wrong Answer

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

count=h*w
row=0
line=0
i=0
j=0
ans=0

while count>0:
    if p[i]>=q[j]:
        ans+=p[i]*(w-line)

        count-=w-line
        i+=1
        row+=1

    else:
        ans+=q[j]*(h-row)

        count-=h-row
        j+=1
        line+=1
x=sum(p)*(h+1)+sum(q)*(w+1)
print(x-ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    w, h = LI()
    a = IR(w + h)
    a.sort()
    acc = list(itertools.accumulate(a))[::-1]
    ans = acc[0]
    for i in range(1, w + h, 2):
        ans += acc[i]
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
from collections import defaultdict as dd
input = sys.stdin.readline
W, H = map(int, input().split())
p = []
q = []
for _ in range(W): p.append(int(input()))
for _ in range(H): q.append(int(input()))
ex = dd(list)
ey = dd(list)
ps = sum(p)
qs = sum(q)
#print(p, q)
for i in range(H):
  ey[i].append((i + H + 1, ps))
  ey[i].append((i + 1, q[i]))
  ey[i + H + 1].append((i + 1 + H + 1, q[i] * W))
ey[H].append((2 * H + 1, ps))
for i in range(W):
  ex[i].append((i + W + 1, qs))
  ex[i].append((i + 1, p[i]))
  ex[i + W + 1].append((i + 1 + W + 1, p[i] * H))
ex[W].append((2 * W + 1, qs))
class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res
prix = prim(2 * (W + 1), ex)
priy = prim(2 * (H + 1), ey)
#print(ex, ey)
print(min(prix.MSTcost(), priy.MSTcost()))
#print(prix.MSTcost(), priy.MSTcost())

Submission status: Wrong Answer

Solution code:
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

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

edges = []
for p in P:
    edges.append((p, 'P'))
for q in Q:
    edges.append((q, 'Q'))
edges.sort()

ans = 0
v_nodes = W + 1
h_nodes = H + 1
for e, pq in edges:
    if pq == 'P':
        ans += e * h_nodes
        v_nodes -= 1
    else:
        ans += e * v_nodes
        h_nodes -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
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

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

P.sort(reverse=True)
Q.sort(reverse=True)

ans = 0
v_nodes = W + 1
h_nodes = H + 1
while P or Q:
    if P and Q:
        if P[-1] < Q[-1]:
            ans += P.pop() * h_nodes
            v_nodes -= 1
        else:
            ans += Q.pop() * v_nodes
            h_nodes -= 1
    elif P:
        ans += P.pop() * h_nodes
        v_nodes -= 1
    elif Q:
        ans += Q.pop() * v_nodes
        h_nodes -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
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

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

P.sort(reverse=True)
Q.sort(reverse=True)

ans = 0
v_nodes = W + 1
h_nodes = H + 1
while P or Q:
    if not Q or (P and P[-1] < Q[-1]):
        ans += P.pop() * h_nodes
        v_nodes -= 1
    else:
        ans += Q.pop() * v_nodes
        h_nodes -= 1
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
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)]

# 横棒
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)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
w,h=map(int,input().split())

W=[]
H=[]
for i in range(w):
    n=int(input())
    W.append(n)
for i in range(h):
    n=int(input())
    H.append(n)
W.append(10**18)
H.append(10**18)

import heapq
heapq.heapify(W)
heapq.heapify(H)

ans=0
for i in range(10**6):
    if (w+1)*H[0]>10**15 and (h+1)*W[0]>10**15:
        break
    else:
        if (w+1)*H[0]>(h+1)*W[0]:
            ans+=(h+1)*W[0]
            w-=1
            heapq.heappop(W)
        else:
            ans+=(w+1)*H[0]
            h-=1
            heapq.heappop(H)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    high, width = map(int, input().split())
    cost_w = [int(input()) for i in range(width)]
    cost_h = [int(input()) for i in range(high)]

    cost_w.sort()
    cost_h.sort()
    check_high, check_width = 0, 0
    width_ind = 0
    ans = 0
    for i in range(high):

        now_high = cost_h[i]
        while width_ind < width:
            if now_high < cost_w[width_ind]:
                break
            ans += (high + 1 - check_high) * cost_w[width_ind]
            check_width += 1
            width_ind += 1

        ans += (width + 1 - check_width) * cost_h[i]
        check_high += 1

        # print(ans)

    ans += sum(cost_w[width_ind:])

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#C問題
#UnionFind
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

import heapq

H,W = map(int,input().split())
PQ = []
for i in range(W+H+1):
    if i == W:
        continue
    pq = int(input())
    heapq.heappush(PQ,[pq,i,i+1])


w = W+1
h = H+1
ans = 0
V = [i for i in range(H+W+2)]

while PQ:
    e,s,t = heapq.heappop(PQ)
    if find(V,s) != find(V,t):
        union(V,s,t)
        if s < W: #P
            ans+=(e*h)
            w-=1
        else:#Q
            ans+=(e*w)
            h-=1
            
print(ans)

Submission status: Wrong Answer

Solution code:
#C問題
#UnionFind
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

import heapq

H,W = map(int,input().split())
PQ = []
for i in range(W+H+1):
    if i == W:
        continue
    pq = int(input())
    heapq.heappush(PQ,[pq,i,i+1])


a = W+1
b = H+1
ans = 0
V = [i for i in range(H+W+2)]

while PQ:
    edge = heapq.heappop(PQ)
    w,s,t = edge[0],edge[1],edge[2]
    if find(V,s) != find(V,t):
        union(V,s,t)
        if s < W+1: #P
            ans+=w*b
            a-=1
        else:#Q
            ans+=w*a
            b-=1
            
print(ans)

Submission status: Wrong Answer

Solution code:
#C問題
#UnionFind(normal)
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

    
"""
実装例
ABC126E 1or2

#E問題
#UnionFind(normal) 
UFコードは省略
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)
"""

import heapq

H,W = map(int,input().split())
PQ = []
P = []
for i in range(W):
    p = int(input())
    P.append([p,i,i+1])
    heapq.heappush(PQ,[p,i,i+1])
Q = []
for i in range(H):
    q = int(input())
    Q.append([q,i,i+1])
    heapq.heappush(PQ,[q,i+W+1,i+W+2])

uf = UnionFind(H+W+2)
a = W+1
b = H+1
ans = 0

while PQ:
    edge = heapq.heappop(PQ)
    w,s,t = edge[0],edge[1],edge[2]
    if not uf.isSameGroup(s,t):
        uf.Unite(s,t)
        if s < W+1: #P
            ans+=w*b
            a-=1
        else:#Q
            ans+=w*a
            b-=1
            
print(ans)

Submission status: Wrong Answer

Solution code:
W,H=map(int,input().split())
p=sorted(int(input())for _ in'_'*W)
p+=10**1000,
q=sorted(int(input())for _ in'_'*H)
q+=10**1000,
z=i=j=0
h,w=H+1,W+1
while i<W or j<H:
	if h*p[i]<w*q[j]:
		z+=h*p[i]
		i+=1
		w-=1
	else:
		z+=w*q[j]
		j+=1
		h-=1
print(z)

Submission status: Wrong Answer

Solution code:
W,H=map(int,input().split())
p=sorted(int(input())for _ in'_'*W)
p+=10**18,
q=sorted(int(input())for _ in'_'*H)
q+=10**18,
z=i=j=0
h,w=H+1,W+1
while i<W or j<H:
	if h*p[i]<w*q[j]:
		z+=h*p[i]
		i+=1
		w-=1
	else:
		z+=w*q[j]
		j+=1
		h-=1
print(z)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
W,H=map(int,input().split())
P=[int(input()) for _ in range(W)]+[float('inf')]
Q=[int(input()) for _ in range(H)]+[float('inf')]
P.sort(reverse=True)
Q.sort(reverse=True)
ans=0
W+=1
H+=1
while True:
    if W==H==1:
        break
    elif W*Q[-1]<=H*P[-1]:
        ans+=W*Q[-1]
        H-=1
        Q.pop()
    else:
        ans+=H*P[-1]
        W-=1
        P.pop()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    X, Y = map(int, line_input())
    p = [0] * X
    q = [0] * Y
    total_cost = 0
    total_sum_p = [0] * (X + 1)
    for x in range(X): 
        p[x] = int(single_input())
        total_cost += p[x]
        total_sum_p[x + 1] = total_sum_p[x] + p[x]
    p.sort()
    
    for y in range(Y): 
        q[y] = int(single_input())
        total_cost += q[y]
    
    for y in range(Y):
        x_smaller_than_y = bisect(p, q[y])
        total_cost += q[y] * (X - x_smaller_than_y) + total_sum_p[x_smaller_than_y]
    return total_cost
  
if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

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

w_cost = [int(input()) for i in range(w)]
h_cost = [int(input()) for i in range(h)]

w_cost = sorted(w_cost, reverse = True)
h_cost = sorted(h_cost, reverse = True)
w_cnt = 0
h_cnt = 0
ans = 0

while True:
    if not w_cost:
        ans += sum(h_cost)   
        break
    elif not h_cost:
        ans += sum(w_cost)
        break
    elif w_cost[-1] < h_cost[-1]:
        ans += w_cost[-1] * (h+1-h_cnt)
        w_cnt += 1
        del w_cost[-1]
    else:
        ans += h_cost[-1] * (w+1-w_cnt)
        h_cnt += 1
        del h_cost[-1]
        
print(ans)

Submission status: Wrong Answer

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

w_cost = [int(input()) for i in range(w)]
h_cost = [int(input()) for i in range(h)]

w_cost = sorted(w_cost, reverse = True)
h_cost = sorted(h_cost, reverse = True)
w_cnt = 0
h_cnt = 0
ans = 0

while True:
    if (not w_cost) and (not h_cost):
        break
    elif not w_cost:
        ans += h_cost[-1] * (w+1-w_cnt)
        h_cnt += 1    
        del h_cost[-1]
    elif not h_cost:
        ans += w_cost[-1] * (h+1-h_cnt)
        w_cnt += 1
        del w_cost[-1]
    elif w_cost[-1] < h_cost[-1]:
        ans += w_cost[-1] * (h+1-h_cnt)
        w_cnt += 1
        del w_cost[-1]
    else:
        ans += h_cost[-1] * (w+1-w_cnt)
        h_cnt += 1    
        del h_cost[-1]
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def calc_min(S, T):
    H = len(S)
    W = len(T)
    ST = sum(T)
    ans = ST
    for i in range(H):
        if S[i] + ST <= (W + 1) * S[i]:
            ans += S[i] + ST
        else:
            ans += (W + 1) * S[i]

    return ans



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [W, H] = [int(input_raw[0]), int(input_raw[1])]
    P = []
    for i in range(W):
        input_raw = read_func().strip().split()
        P.append(int(input_raw[0]))
    Q = []
    for i in range(H):
        input_raw = read_func().strip().split()
        Q.append(int(input_raw[0]))

    print min(calc_min(P, Q), calc_min(Q, P))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H, W = (int(i) for i in input().split())
L = []
for i in range(W):
  L.append((int(input()), 0))
for i in range(H):
  L.append((int(input()), 1))
a = W
b = H
ans = 0
L.sort()
for i in range(H + W):
  if L[i][1] == 0:
    ans += (b+1) * L[i][0]
    a -= 1
  else:
    ans += (a+1) * L[i][0]
    b -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
w,h = list(map(int,input().split()))
pq = []
for i in range(w):
    pq.append((int(input()),0))
for i in range(h):
    pq.append((int(input()),1))
pq.sort()
res = 0
w+=1
h+=1
dic = {0:w,1:h}

for x in pq:
    print(dic[x[1]],x[0])
    res += dic[1-x[1]]*x[0]
    dic[x[1]] -= 1

print(res)

Submission status: Wrong Answer

Solution code:
from numpy import *
from scipy import *
from sys import *

w, h = map(int, input().split())
p = ndarray(w+1, dtype=int)
q = ndarray(h+1, dtype=int)

for i in range(w):
    p[i] = int(input())
for i in range(h):
    q[i] = int(input())
p, q = sort(p), sort(q)
p[w] = maxsize
q[h] = maxsize
ans = 0

i, j = 0, 0
w_, h_ = w+1, h+1
while i < w or j < h:
    if p[i] < q[j]:
        ans += p[i]*h_
        w_ -= 1
        i += 1
    else:
        ans += q[j]*w_
        h_ -= 1
        j += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    w,h = LI()
    p = sorted([I() for _ in range(w)])
    q = sorted([I() for _ in range(h)])
    r = p[0] * (h+1)
    r += q[0] * (w+1)
    r -= max(p[0],q[0])
    pi = 1
    qi = 1
    for i in range(w+h-2):
        if qi == h:
            r += p[pi] * (h-qi+1)
            pi += 1
        elif pi == w:
            r += q[qi] * (w-pi+1)
            qi += 1
        elif p[pi] < q[qi]:
            r += p[pi] * (h-qi+1)
            pi += 1
        else:
            r += q[qi] * (w-pi+1)
            qi += 1

    return r

print(main())

Submission status: Wrong Answer

Solution code:
w,h = map(int,input().split())
arr=[]
for i in range(w):
    arr.append( (int(input()),'p') )
for i in range(h):
    arr.append( (int(input()),'q') )
arr.sort()
print(arr)
ans=0
for a in arr:
    if a[1]=='p':
        ans+=a[0]*(h+1)
        w-=1
    else:
        ans+=a[0]*(w+1)
        h-=1
print(ans)

Submission status: Wrong Answer

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


PI = [input() for i in range(W)]
QI = [input() for i in range(H)]

   
ans = sum(PI)*(H+1)+sum(QI)*(W+1)


PI.sort(reverse=True)
QI.sort(reverse=True)

if W < V:
    for i in range(V-W):
        PI.append(0)
if H < V:
    for i in range(V-H):
        QI.append(0)
 
PII = [H-i for i in range(V)]
QII = [W-i for  i in range(V)]
VII = [H+W-1-i*2 for i in range(V)]

cnt = W*H





pin = 0
qin = 0

while cnt:

    if PI[pin] > QI[qin]:
        use = min(PII[pin],VII[pin],cnt)
        ans -= PI[pin]*use

        PII[pin]-=use
        VII[pin]-=use
        cnt-=use
        pin+=1
    else:
        use = min(QII[qin],VII[qin],cnt)
        ans -= QI[qin]*use

        QII[qin]-=use
        VII[qin]-=use
        cnt-=use
        qin+=1       
print ans