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: Accepted

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):
    ans = sum(P) + sum(Q)

    P.sort()
    Q.sort()
    for q in Q:
        i = bisect.bisect_left(P, q)
        ans += q * (len(P)-i)
    for p in P:
        i = bisect.bisect_right(Q, p)
        ans += p * (len(Q)-i)

    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: Accepted

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 = sum(P) + sum(Q)

    P.sort()
    Q.sort()
    # print(P)
    for q in Q:
        i = bisect.bisect_left(P, q)
        # print(i, q)
        ans += q * (len(P)-i)
    for p in P:
        i = bisect.bisect_right(Q, p)
        # print(i, p)
        ans += p * (len(Q)-i)

    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: Accepted

Solution code:
import heapq
w,h = map(int,input().split())
l = []
for i in range(w):
    p0 = int(input())
    l.append([-1*p0,0])
for i in range(h):
    q0 = int(input())
    l.append([-1*q0,1])
heapq.heapify(l)
wide = 0
high = 0
ans = 0
for i in range(w+h):
    a,b = heapq.heappop(l)
    if b == 0:
        ans += -1*a*(high+1)
        wide += 1
    else:
        ans += -1*a*(wide+1)
        high += 1
print(ans)

Submission status: Accepted

Solution code:
w,h = map(int,input().split())
pq = [[int(input()),0] for _ in range(w)] + [[int(input()),1] for _ in range(h)]
pq.sort()

a = w + 1
b = h + 1
ans = 0
for x,i in pq:
    if i == 0:
        ans += b*x
        a -= 1
    else:
        ans += a*x
        b -= 1

print(ans)

Submission status: Accepted

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

# 解説AC
# クルスカルでどのように最小全域木を作るかというと
# 辺ソートして小さい順に辺を見る
# ↓
# その辺が非連結成分どおしをつなぐなら追加
#
# 今回の場合pi,qjを合わせてソートする
# ↓
# piなら(i+1,y)と(i,y)の要素が連結成分になったとして考えられる
# qjなら(x,j+1)と(x,j)の要素が連結成分になったとして考えられる
# ↑
# これがどういうことかというと今piを辺に追加するとして,追加したなら
# qjによって連結成分になった分のyをつながなくても良い((i+1,y)と(i,y)を
# 連結にする際にすでに(i,y)と(i,y+1)は連結になっているため(i+1,y)と(i,y)を
# 連結にしたら(i+1,y+1) と(i,y)も連結になる))
#
# (5×5)追加する辺は
# x=1, y=1, x=3, x=4, y=3, x=2, y=2, y=4 の順番
#
#         1                       2                        3        
# o   o   o   o   o       o - o   o   o   o        o - o   o   o   o
#                    x=1                     y=1                    
# o   o   o   o   o       o - o   o   o   o        o - o   o   o   o
#                    add                     add                    
# o   o   o   o   o  ==>  o - o   o   o   o  ===>  o - o   o   o   o
#                    plus                    plus                   
# o   o   o   o   o       o - o   o   o   o        o - o   o   o   o
#                    5edg                    4edg      |   |   |   | 
# o   o   o   o   o       o - o   o   o   o        o - o   o   o   o
#
# 
#         3                       4                        5        
# o - o   o   o   o       o - o   o - o   o        o - o   o - o - o
#                    x=3                     x=4                    
# o - o   o   o   o       o - o   o - o   o        o - o   o - o - o
#                    add                     add                    
# o - o   o   o   o  ==>  o - o   o - o   o  ===>  o - o   o - o - o
#                    plus                    plus                   
# o - o   o   o   o       o - o   o - o   o        o - o   o - o   o
#     |   |   |   |  4edg     |   |   |   |  4edg      |   |   |   |
# o - o   o   o   o       o - o   o   o   o        o - o   o   o - o
#
# (4, 5 で共通するようにy = 1か2のやつはどっちでもいい(これが連結になることによる辺を追加しなくて良くなるイメージ))
# 
#         5                       6                        7        
# o - o   o - o - o       o - o   o - o - o        o - o - o - o - o
#                    y=3                     x=2                    
# o - o   o - o - o       o - o   o - o - o        o - o - o - o - o
#                    add      |   |          add       |   |        
# o - o   o - o - o  ==>  o - o   o - o - o  ===>  o - o   o - o - o
#                    plus                    plus                   
# o - o   o - o   o       o - o   o - o   o        o - o - o - o   o
#     |   |   |   |  2edg     |   |   |   |  3edg      |   |   |   |
# o - o   o   o - o       o - o   o   o - o        o - o   o   o - o
#
#
#
#         7                       8                        9        
# o - o - o - o - o       o - o - o - o - o        o - o - o - o - o
#                    y=2                     y=4       |            
# o - o - o - o - o       o - o - o - o - o        o - o - o - o - o
#     |   |          add      |   |          add       |   |        
# o - o   o - o - o  ==>  o - o   o - o - o  ===>  o - o   o - o - o
#                    plus         |          plus          |        
# o - o - o - o   o       o - o - o - o   o        o - o - o - o   o
#     |   |   |   |  1edg     |   |   |   |  1edg      |   |   |   |
# o - o   o   o - o       o - o   o   o - o        o - o   o   o - o
#
# 後はこれを実装するだけ
#
# 二つを合わせてソートするという考えは良かったけどサンプルケースに特化しすぎた。。
# もう少し考察でたどり着きたかった
#  
# solve
def solve():
    w, h = LI()
    a = []
    x, y = 0, 1
    for _ in range(w):
        a.append((II(), x))
    for _ in range(h):
        a.append((II(), y))
    a.sort()
    plus_x = h + 1
    plus_y = w + 1
    ans = 0
    for ai, xy in a:
        if xy:
            ans += ai * plus_y
            plus_x -= 1
        else:
            ans += ai * plus_x
            plus_y -= 1
    print(ans)
    return


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    w,h=map(int,input().split())
    PQ=[None]*(w+h)
    for i in range(w):
        PQ[i]=(int(input()),0)
    for j in range(h):
        PQ[w+j]=(int(input()),1)
    PQ.sort()

    ans=0
    cnt=[h+1,w+1]
    for c,q in PQ:
        ans+=cnt[q]*c
        cnt[1-q]-=1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def main():
    import heapq
    w,h=map(int,input().split())
    p=[int(input()) for _ in [0]*w]
    q=[int(input()) for _ in [0]*h]
    
    cnt1=w+1
    cnt2=h+1

    h=[]
    heapq.heapify(h)
    for i in p:
        heapq.heappush(h,[i,0])
    for i in q:
        heapq.heappush(h,[i,1])

    ans=0
    while h:
        i,j=heapq.heappop(h)
        if j==0:
            ans+=cnt2*i
            cnt1-=1
        else:
            ans+=cnt1*i
            cnt2-=1
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict as dd
input = sys.stdin.readline
W, H = map(int, input().split())
pq = []
for _ in range(W): pq.append((int(input()), 0))
for _ in range(H): pq.append((int(input()), 1))
pq.sort(key = lambda x: -x[0])
a = W + 1
b = H + 1
res = 0
for _ in range(W + H):
  x = pq.pop()
  #print(x)
  if x[1]:
    b -= 1
    res += a * x[0]
  else:
    a -= 1
    res += b * x[0]
  #print(res)
print(res)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    w,h = LI()
    p = IR(w)
    q = IR(h)
    l = []
    for i in p:
        l.append([i,0])
    for i in q:
        l.append([i,1])
    x = 0
    y = 0
    l.sort()
    ans = 0
    for i,j in l:
        if j:
            ans += i*(w+1-x)
            y += 1
        else:
            ans += i*(h+1-y)
            x += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

pq = [(p[i], 0, i) for i in range(W)] + [(q[i], 1, i) for i in range(H)]
pq.sort()

ret = 0
x, y = W + 1, H + 1
for cost, type, i in pq :
    if type == 0 :
        x -= 1
        ret += p[i] * y
    else :
        y -= 1
        ret += q[i] * x
        
print(ret)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
P = [ int(input()) for _ in range(H) ]
Q = [ int(input()) for _ in range(W) ]
E = [(p, 0) for p in P] + [(q, 1) for q in Q]
E.sort()
ans = 0
for e in E:
  if e[1] == 0:
    ans += e[0] * (W+1)
    H -= 1
  if e[1] == 1:
    ans += e[0] * (H+1)
    W -= 1
print(ans)

Submission status: Accepted

Solution code:
W, H = map(int, input().split())
P = [int(input()) for _ in range(W)]
Q = [int(input()) for _ in range(H)]
PQ = P + Q
Idx = list(range(W+H))
Idx.sort(key=lambda x: PQ[x])
ans = 0
p = W+1
q = H+1
for idx in Idx:
    if idx >= W:
        ans += PQ[idx] * p
        q -= 1
    else:
        ans += PQ[idx] * q
        p -= 1
print(ans)

Submission status: Accepted

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


W, H = 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 = P.copy()
# 縦棒
vs = Q.copy()

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]):
        # 横棒を使う
        # まだくっつけてない横軸の数だけ辺を張る
        ans += hs.pop() * h_nodes
        v_nodes -= 1
    else:
        # 縦棒のが短い
        ans += vs.pop() * v_nodes
        h_nodes -= 1
print(ans)

# print(test())

Submission status: Accepted

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ぎゃくだ
W,H = 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
a = W + 1
b = H + 1
for e, pq in edges:
    if pq == 'P':
        ans += e * b
        a -= 1
    else:
        ans += e * a
        b -= 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
w,h = map(int,input().split())
p = [int(input()) for _ in [0]*(w)]
q = [int(input()) for _ in [0]*(h)]

p.sort()

ps = [0,p[0]]
for i in range(1,w):
    ps.append(ps[-1]+p[i])

res = sum(p)
for e in q:
    k = bisect.bisect_right(p,e)
    res += e*(w-k+1) + ps[k]
print(res)

Submission status: Accepted

Solution code:
w,h=map(int,input().split())
e=[]
for _ in range(w):
  c=int(input())
  e.append((c,0))
for _ in range(h):
  c=int(input())
  e.append((c,1))
e=sorted(e,key=lambda x:x[0])
a=w+1
b=h+1
ans=0
for val,flag in e:
  if flag==0:
    ans+=val*b
    a-=1
  else:
    ans+=val*a
    b-=1
print(ans)

Submission status: Accepted

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

side = [{"cost":int(input()), "di":0}for i in range(W)] + [{"cost":int(input()), "di":1}for i in range(H)]
side = sorted(side, key=lambda x:x["cost"])
ans = 0
ty = [H+1,W+1]
for s in side:
    cost, di = s["cost"], s["di"]
    ans += ty[di] * cost
    ty[(di+1)%2] -= 1
print(ans)

Submission status: Accepted

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

W, H = map(int, input().split())
costs = []
for _ in range(W):
    costs.append((int(input()), 0))
for _ in range(H):
    costs.append((int(input()), 1))
costs.sort(key=lambda x: x[0])

h = H+1
w = W+1
ans = 0
for cost, flg in costs:
    if flg == 0:
        ans += cost * h
        w -= 1
    else:
        ans += cost * w
        h -= 1
print(ans)

Submission status: Accepted

Solution code:
W, H = [int(_) for _ in input().split()]
S = []
for _ in range(W):
    S += [(int(input()), 0)]
for _ in range(H):
    S += [(int(input()), 1)]
S.sort()
ans = w = h = 0
for c, d in S:
    if d:
        ans += c * (W + 1 - w)
        h += 1
    else:
        ans += c * (H + 1 - h)
        w += 1
print(ans)

Submission status: Accepted

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

L=[]

for i in range(w):
    n=int(input())
    L.append([n,0])
    
for i in range(h):
    n=int(input())
    L.append([n,1])
    
L.sort()

ans=0
for i in range(len(L)):
    if L[i][1]==0:
        ans+=L[i][0]*(h+1)
        w-=1
    else:
        ans+=L[i][0]*(w+1)
        h-=1
print(ans)

Submission status: Accepted

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

L=[]

for i in range(w):
    n=int(input())
    L.append([n,0])
    
for i in range(h):
    n=int(input())
    L.append([n,1])
    
L.sort()

ans=0
for i in range(len(L)):
    if L[i][1]==0:
        ans+=L[i][0]*(h+1)
        w-=1
    else:
        ans+=L[i][0]*(w+1)
        h-=1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
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)]

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

sP = [0]
a = 0
for p in P:
    a += p
    sP.append(a)

ans = sP[-1]
for q in Q:
    ip = bisect_left(P, q)
    ans += q*(W+1-ip) + sP[ip]
print(ans)

Submission status: Accepted

Solution code:
t,*p=open(0)
w,h=map(int,t.split()) 
c=0
for v,f in sorted((int(t),i<w)for i,t in enumerate(p)):
  c-=~h*v*f or~w*v
  w-=f
  h-=1^f
print(c)

Submission status: Accepted

Solution code:
t,*p=open(0)
w,h=map(int,t.split()) 
c=0
for v,f in sorted((t,i<w)for i,t in enumerate(map(int,p))):
  c-=~h*v*f or~w*v
  w-=f
  h-=1^f
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#CODE FESTIVAL 2016 qual B C
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

w,h = LI()
p = [I() for _ in range(w)]
q = [I() for _ in range(h)]
hq = []
for i in p:
    heappush(hq,(i,0))
for i in q:
    heappush(hq,(i,1))
ans = 0
w += 1
h += 1
while hq:
    v,flg = heappop(hq)
    if flg:
        ans += v*w
        h -= 1
    else:
        ans += v*h
        w -= 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#CODE FESTIVAL 2016 qual B C
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
w,h = LI()
p = [I() for _ in range(w)]
q = [I() for _ in range(h)]
hq = []
for i in p:
    heappush(hq,(i,0))
for i in q:
    heappush(hq,(i,1))
ans = 0
w += 1
h += 1
while hq:
    v,flg = heappop(hq)
    if flg:
        ans += v*w
        h -= 1
    else:
        ans += v*h
        w -= 1
print(ans)

Submission status: Accepted

Solution code:
w,h=map(int,input().split())
s=sorted([[int(input()),0]for i in range(w)]+[[int(input()),1]for i in range(h)])
a,b,c=w+1,h+1,0
for i,j in s:
    if j:
        c+=i*a
        b-=1
    else:
        c+=i*b
        a-=1
print(c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

W,H = map(int,input().split())
P = [int(input()) for _ in range(W)]
Q = [int(input()) for _ in range(H)]

cost = 0
rest_P = W
rest_Q = H
P.sort()
Q.sort()
INF = 10**10
P.append(INF)
Q.append(INF)
p = 0
q = 0
for _ in range(W+H):
    x,y = P[p],Q[q]
    if x < y:
        cost += x * (rest_Q+1)
        p += 1
        rest_P -= 1
    else:
        cost += y * (rest_P+1)
        q += 1
        rest_Q -= 1
print(cost)

Submission status: Accepted

Solution code:
import heapq
W, H = map(int, input().split())
Q = []
for _ in range(W):
  p = int(input())
  heapq.heappush(Q, [p, 0])
for _ in range(H):
  q = int(input())
  heapq.heappush(Q, [q, 1])
cnt = 0
L = [H + 1, W + 1]
while Q:
  c, l = heapq.heappop(Q)
  cnt += c * L[l]
  L[1 - l] -= 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

w, h = getList()

root = []
for i in range(w):
    n = getN()
    root.append((n, 0))

for i in range(h):
    n = getN()
    root.append((n, 1))

root.sort()
w += 1
h += 1
ans = 0
for r in root:
    if r[1] == 0:
        ans += r[0] * h
        w -= 1
    else:
        ans += r[0] * w
        h -= 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
W,H=map(int,input().split())
from heapq import heappush,heappop,heapify
p,q=[int(input()) for i in range(W)],[int(input()) for i in range(H)]
heapify(p),heapify(q)
r,i,j=0,W+1,H+1
while i>1 and j>1:
    if p[0]<q[0]:
        r+=heappop(p)*j
        i-=1
    else:
        r+=heappop(q)*i
        j-=1
print(r+sum(p)+sum(q))

Submission status: Accepted

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

cost = [(int(input()), i, 'r') for i in range(W)] + [(int(input()), i, 'c') for i in range(H)]

cost.sort()
row = H + 1
col = W + 1
ans = 0

for c, i, t in cost:
    if t == 'r':
        ans += max(0, row) * c
        col -= 1
    else:
        ans += max(0, col) * c
        row -= 1

print(ans)

Submission status: Accepted

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():
    width, high = 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

    ans += sum(cost_w[width_ind:])

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

W, H = getlist()
E = []

for i in range(W):
	p = int(input())
	E.append([p, "W"])
for i in range(H):
	q = int(input())
	E.append([q, "H"])
E = sorted(E)

N = H + W
h = H + 1
w = W + 1
ans = 0
for i in range(N):
	if E[i][1] == "W":
		ans += E[i][0] * h
		w -= 1
	else:
		ans += E[i][0] * w
		h -= 1

print(ans)

Submission status: Accepted

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

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

#print(PQ)
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: Accepted

Solution code:
import sys,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

ans = 0
w,h = m()

p = []

for i in range(w):
    k = onem()
    p.append([k,0])
for i in range(h):
    k = onem()
    p.append([k,1])
p.sort()
w,h = w+1,h+1

for i in range(len(p)):
    if p[i][1] == 0:
        ans += h*p[i][0]
        w -= 1
    else:
        ans += w * p[i][0]
        h -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys #入力時間短縮
input = sys.stdin.readline

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
#1マスずつmax(pi,qj)→O(N^2)
#pi,qjが大きい順に列ごと消去→O(N)
for i in range(W+H-1):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()

Submission status: Accepted

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

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W+H):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()

Submission status: Accepted

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 p[i]<q[j]:
		z+=h*p[i]
		i+=1
		w-=1
	else:
		z+=w*q[j]
		j+=1
		h-=1
print(z)

Submission status: Accepted

Solution code:
W, H = map(int, input().split())
D = []
for i in range(W):
    D.append((int(input()), 0))

for i in range(H):
    D.append((int(input()), 1))

D = sorted(D)
A, B = H + 1, W + 1
ans = 0
for i, k in D:
    if k == 0:
        ans += i * A
        B -= 1
    else:
        ans += i * B
        A -= 1

print(ans)

Submission status: Accepted

Solution code:
W,H = map(int,input().split())
PQ = [(int(input()),0) for _ in [0]*W] + [(int(input()),1) for _ in [0]*H]
PQ.sort()
r = H+1
c = W+1
ans = 0
for d,pq in PQ:
    if pq==0:
        ans += d*r
        c -=1
    else:
        ans += d*c
        r -=1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

w, h = map(int, input().split())
r = []
for _ in range(w):
	r.append([int(input()), 0])
for _ in range(h):
	r.append([int(input()), 1])
r.sort(key=lambda x: x[0], reverse=True)
p, q = h+1, w+1
ans, num = 0, 0
while num < (w+1)*(h+1)-1:
	x = r.pop()
	if x[1] == 0:
		num += p
		q -= 1
		ans += x[0]*p
	else:
		num += q
		p -= 1
		ans += x[0]*q

	if num > (w+1)*(h+1)-1:
		ans -= x[0] * (num-(w+1)*(h+1)+1)
print(ans)