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:
W,H = map(int,input().split())
edges = []
for i in range(W):
    p = int(input())
    edges.append((p,0))
for i in range(H):
    q = int(input())
    edges.append((q,1))
edges.sort(key = lambda x:x[0])
ans = 0
w = W+1
h = H+1
for a,b in edges:
    if b == 0:
        w -= 1
        ans += h*a
    else:
        h -= 1
        ans += w*a
print(ans)

Submission status: Accepted

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

E = []
for p in P:
    E.append((p, 0))
for q in Q:
    E.append((q, 1))
E.sort(reverse=True)

a = w+1
b = h+1
ans = 0
while a >1 or b > 1:
    c, t = E.pop()
    if t == 0:
        ans += c*b
        a -= 1
    else:
        ans += c*a
        b -= 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
w, h = map(int, input().split())
p = sorted(int(input()) for _ in range(w))
q = sorted(int(input()) for _ in range(h))


# 全ての(i, j)に対して、min(p[i], q[j])
ans = sum(p) + sum(q)
for i in range(w):
    num = h - bisect_left(q, p[i])
    ans += num * p[i]
for i in range(h):
    num = w - bisect_right(p, q[i])
    ans += num * q[i]
print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(W, H, P, Q):
    E = [(0, p) for p in P] + [(1, q) for q in Q]
    E.sort(key=lambda x: x[1])
    cost = 0
    R = [H + 1, W + 1]
    for d, c in E:
        cost += c * R[d]
        R[d ^ 1] -= 1
    print(cost)

if __name__ == '__main__':
    input = sys.stdin.readline
    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    Q = [int(input()) for _ in range(H)]
    main(W, H, P, Q)

Submission status: Accepted

Solution code:
w, h = list(map(int, input().split()))
xs = [int(input()) for _ in range(w)]
ys = [int(input()) for _ in range(h)]

x_cnt = w + 1
y_cnt = h + 1

i = 0
j = 0
xs.sort()
ys.sort()

ans = 0
while i < len(xs) or j < len(ys):
    if i >= len(xs) or (j < len(ys) and ys[j] < xs[i]):
        ans += x_cnt * ys[j]
        j += 1
        y_cnt -= 1
    else:
        ans += y_cnt * xs[i]
        i += 1
        x_cnt -= 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)]
ans = sum(p) + sum(q)
p.sort(reverse = True)
q.sort(reverse = True)
i = 0
for j in range(w):
    while True:
        if i == h:
            break
        if p[j] >= q[i]:
            break
        i += 1
    ans += i * p[j]
i = 0
for j in range(h):
    while True:
        if i == w:
            break
        if q[j] > p[i]:
            break
        i += 1
    ans += i * q[j]
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[[int(input()),0]for _ in range(n)]
q=[[int(input()),1]for _ in range(m)]
a=p+q
a.sort()
pp=n+1
qq=m+1
ans=0
for x,f in a:
  if f==0:
    ans+=x*qq
    pp=max(0,pp-1)
  else:
    ans+=x*pp
    qq=max(0,qq-1)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
W,H = map(int,input().split())
R = []
for i in range(W):
  temp = int(input())
  heappush(R,(temp,"x"))
for i in range(H):
  temp = int(input())
  heappush(R,(temp,"y"))
X = 0
Y = 0
ans = 0
#print(W,H)
for i in range(H+W):
  cost,muki = heappop(R)
  #print(cost,muki)
  if muki == "x":
    ans += cost*(H+1-Y)
    #print(cost,H+1-Y,muki)
    X += 1
  else:
    ans += cost*(W+1-X)
    #print(cost,W+1-X,muki)
    Y += 1
print(ans)

Submission status: Accepted

Solution code:
w, h = map(int, input().split())
plst = [int(input()) for _ in range(w)]
qlst = [int(input()) for _ in range(h)]
plst.sort()
qlst.sort()
p_cnt = w + 1
q_cnt = h + 1
ppos = 0
qpos = 0
ans = 0
while 1:
    if plst[ppos] < qlst[qpos]:
        ans += plst[ppos] * q_cnt
        p_cnt -= 1
        ppos += 1
        if ppos == w:
            ans += sum(qlst[qpos:])
            break
    else:
        ans += qlst[qpos] * p_cnt
        q_cnt -= 1
        qpos += 1
        if qpos == h:
            ans += sum(plst[ppos:])
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


w,h = list(map(int, input().split()))
p = [None]*(w+h)
for i in range(w):
    p[i] = (int(input()), 0)
for j in range(h):
    p[w+j] = (int(input()), 1)
p.sort()
nums = [h+1,w+1]
ans = 0
i = 0
es = 0
while es<(h+1)*(w+1)-1:# and nums[0]<w+1 and nums[1]<h+1:
    v, d = p[i]
    if nums[d]==0:
        pass
    else:
        ans += v * nums[d]
        es += nums[d]
        nums[int(not d)] -= 1
    i += 1
#     print(ans, nums)
print(ans)

Submission status: Accepted

Solution code:
W,H=map(int,input().split())
P=[int(input()) for i in range(W)]
Q=[int(input()) for i in range(H)]
R=[]
for i in range(W):
  R.append((P[i],0))
for i in range(H):
  R.append((Q[i],1))
P=0
R.sort()
H,W=H+1,W+1
for i in range(len(R)):
  if R[i][1]:
    P+=W*R[i][0]
    H-=1
  else:
    P+=H*R[i][0]
    W-=1
print(P)

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)]
p.sort(reverse=True)
q.sort(reverse=True)
ans=0
c,r=w+1,h+1
while p or q:
  if q and (not p or p[-1]>q[-1]):
    ans+=q.pop()*c
    r-=1
  else:
    ans+=p.pop()*r
    c-=1
print(ans)

Submission status: Accepted

Solution code:
W,H = map(int, input().split())
P = [0] * W
Q = [0] * H
for i in range(W):
  P[i] = int(input())
for i in range(H):
  Q[i] = int(input())
  
P.sort()
Q.sort()

# banhei
infv = int(1e9)
P.append(infv)
Q.append(infv)

cumP = [0] * (W+1)
cumQ = [0] * (H+1)
for i in range(W):
  cumP[i+1] = cumP[i] + P[i]
for i in range(H):
  cumQ[i+1] = cumQ[i] + Q[i]
  
#print(cumP)
#print(cumQ)
y,x = 0,0
cost = 0
while y <= H and x <= W:
  #print(x,y)
  # 右か下にコストが安いほうにいけばよい。イコールなら任意でよい。
  if x == W and y == H:
    break
  elif P[x] <= Q[y]:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  else:
    cost += Q[y]
    y += 1
    cost += cumP[x]
    
print(cost)

Submission status: Accepted

Solution code:
W,H = map(int, input().split())
P = [0] * W
Q = [0] * H
for i in range(W):
  P[i] = int(input())
for i in range(H):
  Q[i] = int(input())
  
P.sort()
Q.sort()
cumP = [0] * (W+1)
cumQ = [0] * (H+1)
for i in range(W):
  cumP[i+1] = cumP[i] + P[i]
for i in range(H):
  cumQ[i+1] = cumQ[i] + Q[i]
  
#print(cumP)
#print(cumQ)
y,x = 0,0
cost = 0
while y <= H and x <= W:
  #print(x,y)
  # 右か下にコストが安いほうにいけばよい。イコールなら任意でよい。
  if x == W and y == H:
    break
  elif x == W:
    cost += Q[y]
    y += 1
    cost += cumP[x]    
  elif y == H:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  elif P[x] <= Q[y]:
    cost += P[x]
    x += 1
    cost += cumQ[y]
  else:
    cost += Q[y]
    y += 1
    cost += cumP[x]
    
print(cost)

Submission status: Accepted

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

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

w,h = inm()
p = []
q = []
for i in range(w):
    p.append(inn())
for i in range(h):
    q.append(inn())
x = w+1
y = h+1
p.sort(reverse=True)
q.sort(reverse=True)
ans = 0
while x>1 or y>1:
    #ddprint(f"{x=} {y=} {p} {q}")
    if x>1 and (y==1 or p[-1]<=q[-1]):
        ans += p[-1]*y
        p.pop()
        x -= 1
    else:
        ans += q[-1]*x
        q.pop()
        y -= 1
print(ans)

Submission status: Accepted

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

q.sort()
q_cum = [0 for _ in range(h+1)]
for i in range(h):
    q_cum[i+1] = q_cum[i] + q[i]

ans = sum(q)
for i in range(w):
    x = bisect.bisect_left(q, p[i])
    ans += q_cum[x] + p[i] * (h + 1 - x)

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.buffer.readline

W, H = map(int, input().split())
ps = sorted(int(input()) for _ in range(W))
qs = sorted(int(input()) for _ in range(H))

# Add [0] to satisfy "q_cumsum[index] = sum(q[:index])".
q_cumsum = np.cumsum([0] + qs)

ans = sum(ps) + q_cumsum[-1]

index = 0
for p in ps:
    while index < H and qs[index] <= p:
        index += 1
    ans += q_cumsum[index] + p * (H - index)
    
print(ans)

Submission status: Accepted

Solution code:
# クラスかるほう
# 　貪欲に辺ごとにソートをしてとけばいい
W, H = map(int, input().split())
d = []
for i in range(W):
    x = int(input())
    d.append((x, 0))

for j in range(H):
    y = int(input())
    d.append((y, 1))
d.sort()
X = H+1
Y = W+1

ans = 0

for que in d:
    weight, pos = que
    if pos <1:
        ans += X*weight
        Y -= 1
    else:
        ans += Y*weight
        X -= 1
print(ans)

Submission status: Accepted

Solution code:
# クラスかるほう
# 　貪欲に辺ごとにソートをしてとけばいい
W, H = map(int, input().split())
d = []
for i in range(W):
    x = int(input())
    d.append((x, "x"))

for j in range(H):
    y = int(input())
    d.append((y, "y"))
d.sort()
X = H+1
Y = W+1

ans = 0

for que in d:
    weight, pos = que
    if pos == "x":
        ans += X*weight
        Y -= 1
    else:
        ans += Y*weight
        X -= 1
print(ans)

Submission status: Accepted

Solution code:
W,H,*L = map(int, open(0).read().split())
ls = [0]*(W+H)
for i,c in enumerate(L):
  if i<W:
    ls[i] = (c,0)
  else:
    ls[i] = (c,1)
ls.sort()
P = 0
Q = 0
cnt = (W+1)*(H+1)-1
ans = 0
for c,s in ls:
  if s:
    m = min(cnt,W+1-P)
    cnt -= m
    ans += m*c
    Q += 1
  else:
    m = min(cnt,H+1-Q)
    cnt -= m
    ans += m*c
    P += 1
  if cnt==0:
    print(ans)
    break

Submission status: Accepted

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

W, H = map(int, input().split())
p = [int(input()) for i in range(W)]
q = [int(input()) for i in range(H)]
p.sort()
q.sort()
row = H + 1
col = W + 1
i = j = 0
ans = 0
while row > 1 or col > 1:
    if i < W and (j == H or p[i] < q[j]):
        ans += p[i] * row
        col -= 1
        i += 1
    else:
        ans += q[j] * col
        row -= 1
        j += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

W,H = LI()
p = LIR(W,1)
q = LIR(H,1)

p.sort()
cusum = [p[0]]
for i in range(1,W):
    cusum.append(cusum[-1]+p[i])
ans = cusum[-1]

for i in range(H):
    place = bisect_left(p,q[i])
    temp = cusum[place-1] if place >= 1 else 0
    ans += temp + q[i]*(W+1-place)

print(ans)

Submission status: Accepted

Solution code:
w,h= map(int,input().split())
p = sorted([int(input()) for _ in range(w)],reverse=True)
q = sorted([int(input()) for _ in range(h)],reverse=True)
sumrp = [0]*w
sumrp[-1]=p[-1]
for i in range(w-2,-1,-1):sumrp[i]=sumrp[i+1]+p[i]
sumrq = [0]*h
sumrq[-1]=q[-1]
for i in range(h-2,-1,-1):sumrq[i]=sumrq[i+1]+q[i]
gen=0
pid = qid = 0
w+=1
h+=1
while True:
    if pid==w-1:
        gen+=sumrq[qid]
        break
    if qid==h-1:
        gen+=sumrp[pid]
        break
    if p[pid]>=q[qid]:
        gen+=p[pid]
        gen+=sumrq[qid]
        pid+=1
    elif p[pid]<q[qid]:
        gen+=q[qid]
        gen+=sumrp[pid]
        qid+=1
print(gen)

Submission status: Accepted

Solution code:
import heapq

W, H = map(int, input().split(" "))
que = []
for _ in range(W):
    heapq.heappush(que, (int(input()), 'W'))

for _ in range(H):
    heapq.heappush(que, (int(input()), 'H'))

W += 1
H += 1
ans = 0
while que:
    cost, pos = heapq.heappop(que)
    if pos == 'W':
        ans += cost * H
        W -= 1
    else:
        ans += cost * W
        H -= 1

print(ans)

Submission status: Accepted

Solution code:

w,h = list(map(int, input().split()))
ws = []
hs = []
for i in range(w): ws.append(int(input()))
for i in range(h): hs.append(int(input()))

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

remainW = w
remainH = h
aliveW = [1 for i in range(w)]
aliveH = [1 for i in range(h)]

ans = 0
while(remainW>0 or remainH>0):
    #print(ans, remainW, remainH)
    costW = ws[remainW-1] * (remainH + 1)
    costH = hs[remainH-1] * (remainW + 1)
    if(remainH!=0 and (ws[remainW-1] > hs[remainH-1] or remainW==0)):
        ans += costH
        remainH = max(0,remainH-1)
    else:
        ans += costW
        remainW = max(0,remainW-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline

W, H, *pq = map(int, read().split())
pq = list(zip(pq[:W], ['p'] * W)) + list(zip(pq[W:], ['q'] * H))
pq.sort(key=itemgetter(0))
answer = 0
x = W + 1
y = H + 1
for cost, i in pq:
    if i == 'p':
        answer += cost * y
        x -= 1
    else:
        answer += cost * x
        y -= 1

print(answer)

Submission status: Accepted

Solution code:
W, H = map(int, input().split())
PQ = [[int(input()), 'x'] for w in range(W)]
PQ += [[int(input()), 'y'] for h in range(H)]
PQ.sort()

_W = W + 1; _H = H + 1
ans = 0
for v, z in PQ:
  if z == 'x':
    if _W > 1:
      ans += _H * v
      _W -= 1
  else: # z == 'y'
    if _H > 1:
      ans += _W * v
      _H -= 1
  
  if _W == _H == 1:
    break

print(ans)

Submission status: Accepted

Solution code:
import itertools
import bisect

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

P.sort()
accum_P = list(itertools.accumulate(P))
ans = accum_P[-1]
for q in Q:
  idx = bisect.bisect_left(P, q)
  if idx >= W + 1:
    ans += accum_P[W-1] + q
  elif idx == 0:
    ans += (W + 1) * q
  else:
    ans += accum_P[idx-1] + (W + 1 - idx)*q

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

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

P.sort()
Q.sort()

res = 0

for i in range(W):
    res += (H + 1 - bisect_left(Q, P[i])) * P[i]

for i in range(H):
    res += (W + 1 - bisect_right(P, Q[i])) * Q[i]
    
print(res)

Submission status: Accepted

Solution code:
import sys

w, h, *pq = map(int, sys.stdin.buffer.read().split())
vertical_split = 0
horizontal_split = 0
costs = []
costs.extend((p, 0) for p in pq[:w])
costs.extend((q, 1) for q in pq[w:])
costs.sort(reverse=True)

ans = 0
for c, t in costs:
    if t == 0:
        ans += c * (horizontal_split + 1)
        vertical_split += 1
    else:
        ans += c * (vertical_split + 1)
        horizontal_split += 1
print(ans)

Submission status: Accepted

Solution code:
W, H, *L = map(int, open(0).read().split())
p = L[:W]
q = L[W:]
H += 1
W += 1
h = 0
w = 0
ls = [(c,0) for c in p]+[(c,1) for c in q]
ls.sort()
ans = 0
for c,s in ls:
  if s==1:
    ans += c*(W-w)
    h += 1
  if s==0:
    ans += c*(H-h)
    w += 1
print(ans)

Submission status: Accepted

Solution code:
w,h=map(int, input().split())
a=[int(input())for i in range(w)]
b=[int(input())for i in range(h)]
from heapq import heappop,heappush
q=[]
w+=1
h+=1
for i in a:
  heappush(q,(i,0))
for i in b:
  heappush(q,(i,1))
ans=0
while q:
  c,t=heappop(q)
  if t==0:
    ans+=h*c
    w-=1
  else:
    ans+=w*c
    h-=1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    w, h = map(int, input().split())
    pq = [None] * (w + h)

    # KeyInsight:
    # 全域最小木: 任意の2点を行き来できる&コストを最小化する問題
    # ◯: コストを昇順に並び替える
    # ×: 各コストが何本該当するか?
    for i in range(w + h):
        if i < w:
            pq[i] = (int(input()), 'x')
        else:
            pq[i] = (int(input()), 'y')

    x_count = w + 1
    y_count = h + 1
    ans = 0

    # 一つ道路を舗装すると、片方の座標の辺の数が一つ減る
    # abst: 連結成分を作ると、幅が一つ減る
    # 図のイメージは、以下のURLを参照
    # https://scrapbox.io/ganariya/AtCoderCODEFESTIVAL2016qualB_C%E5%95%8F%E9%A1%8C500%E7%82%B9_%E3%80%8CC_-_Gr-idian_MST%E3%80%8D
    for cost, flag in sorted(pq):
        if flag == 'x':
            ans += cost * y_count
            x_count -= 1
        else:
            ans += cost * x_count
            y_count -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    w, h = map(int, input().split())
    pq = [None] * (w + h)

    for i in range(w + h):
        if i < w:
            pq[i] = (int(input()), 'x')
        else:
            pq[i] = (int(input()), 'y')

    x_count = w + 1
    y_count = h + 1
    ans = 0

    for cost, flag in sorted(pq):
        if flag == 'x':
            ans += cost * y_count
            x_count -= 1
        else:
            ans += cost * x_count
            y_count -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

W, H = lr()
P = [ir() for _ in range(W)]
Q = [ir() for _ in range(H)]
P.sort()
Q.sort()
answer = 0
for p in P:
    i = bisect_left(Q, p)
    answer += (H - i + 1) * p

for q in Q:
    i = bisect_right(P, q)
    answer += (W - i + 1) * q

print(answer)
# 19

Submission status: Accepted

Solution code:
w, h = [int(i) for i in input().split()]
p = [(int(input()),0) for _ in range(w)]
q = [(int(input()),1) for _ in range(h)]
pq = sorted(p + q)
hh = 0
ww = 0
ans = 0
for i in pq:
    if i[1] == 0:
        ans += i[0] * (h+1 - hh)
        ww += 1
    else:
        ans += i[0] * (w+1- ww)
        hh += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
w,h = map(int,input().split())
a = [10**18]+[int(input()) for i in range(w)]
b = [10**18]+[int(input()) for i in range(h)]
a.sort(reverse=True)
b.sort(reverse=True)
ans = 0
while len(a)>1 or len(b)>1:
  if a[-1]<b[-1]:
    ans += a[-1]*len(b)
    a.pop()
  else:
    ans += b[-1]*len(a)
    b.pop()
print(ans)

Submission status: Accepted

Solution code:
w,h = map(int,input().split())
a = [10**18]+[int(input()) for i in range(w)]
b = [10**18]+[int(input()) for i in range(h)]
a.sort(reverse=True)
b.sort(reverse=True)
ans = 0
while len(a)>1 or len(b)>1:
  if a[-1]<b[-1]:
    ans += a[-1]*len(b)
    a.pop()
  else:
    ans += b[-1]*len(a)
    b.pop()
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    W,H = map(int,input().split())
    l = []
    for _ in range(W):
        p = int(input())
        l.append((p,0))
    for _ in range(H):
        p = int(input())
        l.append((p,1))
        
    l.sort(key=itemgetter(0))
    a,b = W+1,H+1
    ans = 0
    for d,now in l:
        if now == 0:
            ans += d*b
            a -= 1
        else:
            ans += d*a
            b -= 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

inf = 10**10
yoko = [inf]
tate = [inf]

for _ in range(W):
    p = int(input())
    heapq.heappush(yoko, p)
for _ in range(H):
    p = int(input())
    heapq.heappush(tate, p)

#どこに引くかはあんまり関係ない
#短いやつを使えるだけ使うと良いぞ
ans = 0
while H > 0 or W > 0:
    if yoko[0] < tate[0]:
        ans += (H+1) * heapq.heappop(yoko)
        W -= 1
    else:
        ans += (W+1) * heapq.heappop(tate)
        H -= 1

print(ans)

Submission status: Accepted

Solution code:
def main():
	w, h, *L = map(int, open(0).read().split())
	x, y, ans = w, h, 0
	for c in sorted(L[:w] + [-q for q in L[w:]], key=abs):
		if c > 0:
			if x:
				ans += c * (y + 1)
				x -= 1
		else:
			if y:
				ans -= c * (x + 1)
				y -= 1
		if x == y == 0:
			break
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
w,h,*L=map(int,open(0).read().split())
P=L[:w];Q=[-qj for qj in L[w:]]
x,y,ans=w,h,0
for c in sorted(P+Q,key=abs):
	if c>0:
		if x:ans+=c*(y+1);x-=1
	else:
		if y:ans-=c*(x+1);y-=1
print(ans)

Submission status: Accepted

Solution code:
w,h,*L=map(int,open(0).read().split())
P=L[:w];Q=L[w:]
x,y=w,h
sss=[]
for i,pi in enumerate(P):
	sss.append((pi,1))
for j,qj in enumerate(Q):
	sss.append((qj,0))
sss.sort()
ans=0
for c,f in sss:
	if f and x:
		x-=1
		ans+=c*(y+1)
	elif not f and y:
		y-=1
		ans+=c*(x+1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    W,H=map(int, input().split())
    P=sorted(int(input())for _ in range(W))
    Q=sorted(int(input())for _ in range(H))
    i,j,ans=0,0,0
    while i<W and j<H:
        if P[i]<Q[j]:
            ans+=P[i]*(H-j+1)
            i+=1
        else:
            ans+=Q[j]*(W-i+1)
            j+=1
    while i<W:
        ans+=P[i]*(H-j+1)
        i+=1
    while j<H:
        ans+=Q[j]*(W-i+1)
        j+=1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
w, h = map(int, input().split())
P = [int(input()) for _ in range(w)]
Q = [int(input()) for _ in range(h)]
heapq.heapify(P)
heapq.heapify(Q)
ans = 0
count_x, count_y = 0, 0
while P or Q:
  if not P:
    temp = heapq.heappop(Q)
    ans += temp * (w+1-count_x)
    count_y += 1
  elif not Q:
    temp = heapq.heappop(P)
    ans += temp * (h+1-count_y)
    count_x += 1
  else:
    tp, tq = P[0], Q[0]
    if tp < tq:
      temp = heapq.heappop(P)
      ans += temp * (h+1-count_y)
      count_x += 1
    else:
      temp = heapq.heappop(Q)
      ans += temp * (w+1-count_x)
      count_y += 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)]
edges = []
for i in range(W):
    edges.append((p[i], 0))
for i in range(H):
    edges.append((q[i], 1))
edges.sort()
cnt_h = 0
cnt_w = 0
res = 0
for c, d in edges:
    if d == 0:
        cnt_w+=1
        res+=(H+1-cnt_h)*c
    else:
        cnt_h+=1
        res+=(W+1-cnt_w)*c
print(res)

Submission status: Accepted

Solution code:
w,h=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=w*h
row=0
line=0
i=0
j=0
ans=0

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
w, h = map(int,input().split())
P = [int(input()) for i in range(w)]
Q = [int(input()) for i in range(h)]
R = [P, Q]

nn = [w+1, h+1]
A = []
for i in range(w):
    A.append([P[i], i, 0])
for i in range(h):
    A.append([Q[i], i, 1])

A.sort()
ans = 0
for i in range(len(A)):
    d = A[i][0]
    j = A[i][1]
    t = A[i][2]
    ans += d * nn[(t+1)%2]
    # print(d, nn[(t+1)%2])
    nn[t] = max(1, nn[t]-1)
    if nn == [1, 1]:
        break
print(ans)

Submission status: Accepted

Solution code:
def examA():
    S = SI(); N = len(S)
    T = "CODEFESTIVAL2016"
    ans = 0
    for i in range(N):
        if S[i]!=T[i]:
            ans +=1
    print(ans)
    return

def examB():
    N, A, B = LI()
    S = SI()
    d = defaultdict(int)
    for s in S:
        if s=="a":
            if d["a"]+d["b"]<A+B:
                print("Yes")
                d[s] += 1
            else:
                print("No")
        elif s=="b":
            if d["a"]+d["b"]<A+B and d["b"]<B:
                print("Yes")
                d[s] += 1
            else:
                print("No")
        else:
            print("No")
    return

def examC():
    W, H = LI()
    P = [I() for _ in range(W)]; P.sort()
    Q = [I() for _ in range(H)]; Q.sort()
    dh = 0; dw = 0
    p = 0; q = 0
    ans = 0
    for i in range(H+W):
        if (q<H and p<W and P[p]<Q[q]) or not q<H:
            ans += P[p]*(H+1-dh)
            p +=1; dw +=1
        else:
            ans += Q[q]*(W+1-dw)
            q +=1; dh+=1
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET, _ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 1e-9
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:

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

t = H+1
y = W+1

ans = 0

lis = []

for i in range(W):
    p = int(input())
    lis.append([p,"y",i])

for i in range(H):
    q = int(input())
    lis.append([q,"t",i])

lis.sort()

for i in lis:

    ncost = i[0]
    ndir = i[1]
    #print (i,ans)

    if ndir == "t":
        t -= 1
        ans += ncost * max(0 , y)

    else:
        y -= 1
        ans += ncost * max(0 , t)

print (ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_right

    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    P.sort()
    P_count = [0] * (W + 2)

    Q = [int(input()) for _ in range(H)]
    Q.sort()

    ans = 0
    for q in Q:
        tmp = bisect_right(P, q)
        P_count[tmp] += 1
        ans += q * (1 + W - tmp)

    for i in range(W, - 1, -1):
        P_count[i] += P_count[i + 1]

    for index, p in enumerate(P):
        ans += p * (P_count[index + 1] + 1)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right


    W, H = map(int, input().split())
    P = [int(input()) for _ in range(W)]
    P.sort()
    P_count = [0] * (W + 2)

    Q = [int(input()) for _ in range(H)]
    Q.sort()

    ans = 0
    for q in Q:
        tmp = bisect_right(P, q)
        P_count[tmp] += 1
        ans += q * (1 + W - tmp)

    for i in range(W, - 1, -1):
        P_count[i] += P_count[i + 1]
    # print ('途中', ans)
    # for p in P:
    #     tmp = bisect_left(Q, p)
    #     ans += p * (1 + H - tmp)
    for index, p in enumerate(P):
        ans += p * (P_count[index + 1] + 1)
    print (ans)
    # print ('P:', P)
    # print ('Q:', Q)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right


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

    Q = [int(input()) for _ in range(H)]
    Q.sort()

    ans = 0
    for q in Q:
        tmp = bisect_right(P, q)
        # print ('tmp=', tmp)
        ans += q * (1 + W - tmp)
        # print (ans)

    for p in P:
        tmp = bisect_left(Q, p)
        ans += p * (1 + H - tmp)

    print (ans)
    # print ('P:', P)
    # print ('Q:', Q)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


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

Q = [int(input()) for _ in range(H)]
Q.sort()

ans = 0
for q in Q:
    tmp = bisect_right(P, q)
    # print ('tmp=', tmp)
    ans += q * (1 + W - tmp)
    # print (ans)

for p in P:
    tmp = bisect_left(Q, p)
    ans += p * (1 + H - tmp)

print (ans)
# print ('P:', P)
# print ('Q:', Q)