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:
from heapq import heappush, heappop


def main():
    W, H = map(int, input().split())
    h = []
    for _ in range(W):
        p = int(input())
        heappush(h, (p, 0))
    for _ in range(H):
        q = int(input())
        heappush(h, (q, 1))
    ans = 0
    while len(h):
        v, d = heappop(h)
        if d == 0:
            ans += v * (H+1)
            W -= 1
        else:
            ans += v * (W+1)
            H -= 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce

# 入力
W, H = map(int, input().split())
p = [int(input()) for _ in range(W)]
q = [int(input()) for _ in range(H)]

# クラスカル法に基づいて解を求める
ans, _, _ = reduce(
    lambda acc, c: (
        (
            acc[0] + (H - acc[2] + 1) * c[0] if c[1] == 0 else
            acc[0] + (W - acc[1] + 1) * c[0]
        ),
        (
            acc[1] + 1 if c[1] == 0 else
            acc[1]
        ),
        (
            acc[2] + 1 if c[1] == 1 else
            acc[2]
        )
    ),
    sorted([(P, 0) for P in p] + [(Q, 1) for Q in q]),
    (0, 0, 0)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
w,h=map(int,input().split())
P=[float('inf')]+[int(input()) for _ in range(w)]
Q=[float('inf')]+[int(input()) for _ in range(h)]
P.sort(reverse=True); Q.sort(reverse=True)
ans=0
while w or h:
    if P[-1]<Q[-1] or (P[-1]==Q[-1] and w>=h):
        c=P.pop()
        ans+=c*(h+1)
        w-=1
    else:
        c=Q.pop()
        ans+=c*(w+1)
        h-=1
print(ans)

Submission status: Accepted

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 Q[-1]<P[-1] or (Q[-1]==P[-1] and W<=H):
        ans+=W*Q[-1]
        H-=1
        Q.pop()
    elif Q[-1]>P[-1] or (Q[-1]==P[-1] and W>H):
        ans+=H*P[-1]
        W-=1
        P.pop()
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop
w,h = map(int, input().split())
heap = []
for i in range(w):
    p = int(input())
    heap.append((p,0))
for i in range(h):
    q = int(input())
    heap.append((q,1))
heapify(heap)

ans = 0
h += 1
w += 1
while heap:
    c, f = heappop(heap)
    if f==0:
        ans += c*h
        w -= 1
    else:
        ans += c*w
        h -= 1
print(ans)

Submission status: Accepted

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

    total_cost = 0
    for x in range(X): 
        p[x] = int(single_input())
        total_cost += p[x]
    p.sort()    
    total_sum_p = [0] * (X + 1)
    for x in range(X):
        total_sum_p[x+1] = total_sum_p[x] + p[x]
    
    for y in range(Y): 
        q = int(single_input())
        total_cost += q
        x_smaller_than_y = bisect(p, q)
        total_cost += q * (X - x_smaller_than_y) + total_sum_p[x_smaller_than_y]

    return total_cost
  
if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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
    for x in range(X): p[x] = int(single_input())
    for y in range(Y): q[y] = int(single_input())
    total_cost = sum(p) + sum(q)
    p.sort()
    total_sum_p = [0] * (X + 1)
    for x in range(X):
        total_sum_p[x+1] = p[x] + total_sum_p[x]
    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: Accepted

Solution code:
W,H = (int(num) for num in input().split())
p = [int(input()) for _ in range(W)]
p.sort()
q = [int(input()) for _ in range(H)]
q.sort()
p_cnt = H+1 #何本取るか
q_cnt = W+1
gr_cnt = (W+1) * (H+1) - 1
p_idx = 0
q_idx = 0
ans = 0

while gr_cnt > 0:
    if (p_idx < W and q_idx < H and p[p_idx] <= q[q_idx]) or q_idx >= H:
        nt = min(p_cnt,gr_cnt)
        #print(gr_cnt,nt,p[p_idx])
        ans += p[p_idx] * nt
        gr_cnt -= nt
        q_cnt -= 1
        p_idx += 1
    elif (p_idx < W and q_idx < H and p[p_idx] > q[q_idx]) or p_idx >= W:
        nt = min(q_cnt,gr_cnt)
        #print(gr_cnt,nt,q[q_idx])
        ans += q[q_idx] * nt
        gr_cnt -= nt
        p_cnt -= 1
        q_idx += 1
    
        
print(ans)

Submission status: Accepted

Solution code:
w, h = 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: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

W,H=MAP()
P=[(INT(), 'p') for i in range(W)]
Q=[(INT(), 'q') for i in range(H)]

# 行列をまとめて、コストが低い方から進める
PQ=P+Q
PQ.sort()

a=H+1
b=W+1
ans=0
for i in range(W+H):
    val,_type=PQ[i]
    if _type=='p':
        # 横線を行数に応じて足して、列数を1つ減らす
        ans+=a*val
        b-=1
    else:
        # 縦線を列数に応じて足して、行数を1つ減らす
        ans+=b*val
        a-=1
print(ans)

Submission status: Accepted

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

import sys
from bisect import bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

W,H=MAP()
P=[INT() for i in range(W)]
Q=[INT() for i in range(H)]

P.sort()
Q.sort()

ans=0
for i in range(W):
    cnt=H+1-bisect_left(Q, P[i])
    ans+=cnt*P[i]
for i in range(H):
    cnt=W+1-bisect_right(P, Q[i])
    ans+=cnt*Q[i]
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 j in range(H)]
P.append(float('inf'))
Q.append(float('inf'))
P.sort(reverse=True)
Q.sort(reverse=True)
now_W=W+1
now_H=H+1
cost=0
while now_W>1 or now_H>1:
    if P[-1]<Q[-1]:
        cost+=P.pop()*now_H
        now_W-=1
    elif Q[-1]<P[-1]:
        cost+=Q.pop()*now_W
        now_H-=1
    elif P[-1]==Q[-1]:
        if now_W<=now_H:
            cost+=Q.pop()*now_W
            now_H-=1
        elif now_W>now_H:
            cost+=P.pop()*now_H
            now_W-=1
print(cost)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left
W, H = map(int, input().split())
W_cost = sorted([int(input()) for i in range(W)])
H_cost = [int(input()) for i in range(H)]


# 横は全部辺を張り、縦は各区間1本
W_cost_sum = sum(W_cost)
ans = W_cost_sum * (H + 1) + sum(H_cost)


W_acc_cost = [0] + list(accumulate(W_cost))
for h in H_cost:
    hx = bisect_left(W_cost, h)
    ans -= (W_cost_sum - W_acc_cost[hx]) - ((W - hx) * h)

print(ans)

Submission status: Accepted

Solution code:
import sys

W, H = map(int, input().split())
Xs = [int(sys.stdin.readline()) for _ in range(W)] + [10**9]
Ys = [int(sys.stdin.readline()) for _ in range(H)] + [10**9]

Xs.sort()
Ys.sort()

ans = 0
iX = iY = 0
for _ in range(W+H):
    if Xs[iX] <= Ys[iY]:
        ans += Xs[iX] * (H-iY+1)
        iX += 1
    else:
        ans += Ys[iY] * (W-iX+1)
        iY += 1

print(ans)

Submission status: Accepted

Solution code:
W, H = (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: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[w,h]=i2()
p=[]
q=[]
import bisect
for i in range(w):
 p.append(i1())
for i in range(h):
 q.append(i1())
x=p[:]
x.sort()
d=[x[i] for i in range(w)]
for i in range(w-1):
  d[i+1]+=d[i]
ans=0
for i in range(h):
 dd=bisect.bisect_right(x,q[i])
 if dd>0:
    ans+=d[dd-1]

 ans+=(w-dd)*q[i]
for i in range(h):
 ans+=q[i]
print(ans+d[w-1])

Submission status: Accepted

Solution code:
W,H=map(int,input().split())
List=[]
for i in range(W):
  p=int(input())
  List.append((p,"W"))
for j in range(H):
  q=int(input())
  List.append((q,"H"))
ans=0
List.sort()
for a,l in List:
  if l=="W":
    ans+=(H+1)*a
    W-=1
  elif l=="H":
    ans+=(W+1)*a
    H-=1
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)]
c=sorted([(i,0) for i in p]+[(j,1) for j in q])
a=W+1
b=H+1
ans=0
for z in c:
    if z[1]==0:
        ans+=z[0]*b
        a-=1
    else:
        ans+=z[0]*a
        b-=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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


a = []
for i in range(W):
    a.append(("p", i, p[i]))
for j in range(H):
    a.append(("q", j, q[j]))


a.sort(key=lambda x: x[2])


p_used = 0
q_used = 0
count = 0
cost = 0
i = 0
while True:
    now = a[i]
    if now[0] == "p":
        now_count = H+1 - q_used
        if count + now_count > (W+1)*(H+1) - 1:
            now_count = (W+1)*(H+1) - 1 - count
        count += now_count
        cost += now[2] * now_count
        p_used += 1
    else:
        now_count = W+1 - p_used
        if count + now_count > (W+1)*(H+1) - 1:
            now_count = (W+1)*(H+1) - 1 - count
        count += now_count
        cost += now[2] * now_count
        q_used += 1
    if count == (W+1)*(H+1) - 1:
        break
    i += 1
debug(count)
print(cost)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

W, H = inpl()
p = [(int(input()), 0) for _ in range(W)]
q = [(int(input()), 1) for _ in range(H)]
pq = sorted(p+q)
cW = W+1
cH = H+1
ans = 0
for i, j in pq:
    if j == 1:
        ans += i*cW
        cH -= 1
    else:
        ans += i*cH
        cW -= 1
print(ans)

Submission status: Accepted

Solution code:
W,H=map(int,input().split())
p=[(int(input()),0) for i in range(W)]
q=[(int(input()),1) for i in range(H)]
r=sorted(p+q)
a=W+1
b=H+1
ans=0
for seq in r:
    wt,idx=seq
    if idx==0:
        a-=1
        ans+=b*wt
    else:
        b-=1
        ans+=a*wt
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


w,h = li()
stack = []
for _ in range(w):
    stack.append((ni(),0))
    
for _ in range(h):
    stack.append((ni(),1))
    
    
stack.sort(reverse=True)

res_w = 0
res_h = 0

ans = 0

while res_w <= w and res_h <= h and stack:
    cost, wh = stack.pop()

    if wh == 0:
        ans += (cost * ((h+1)-res_h))
        res_w += 1
        
    else:
        ans += (cost * ((w+1)-res_w))
        res_h += 1

        
print(ans)

Submission status: Accepted

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

E = sorted(P + Q)
used = [W + 1, H + 1]

ans = 0
for e, f in E:
    ans += e * used[1 - f]
    used[f] -= 1

print(ans)

Submission status: Accepted

Solution code:
w,h=map(int,input().split())
n=lambda :int(input())
pq=[]
for _ in range(w):
  pq.append((n(),0))
for _ in range(h):
  pq.append((n(),1))
pq.sort()
w,h=w+1,h+1
ans=0
for i,j in pq:
  if j:
    ans+=i*w
    h-=1
  else:
    ans+=i*h
    w-=1
print(ans)

Submission status: Accepted

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

es = []
for p in ps:
    es.append((p,0))
for q in qs:
    es.append((q,1))
es.sort()

ans = 0
xn,yn = W+1,H+1
for d,t in es:
    if t:
        ans += d * xn
        yn -= 1
    else:
        ans += d * yn
        xn -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

W,H = inpl()
Lines = []
for i in range(W):
	Lines.append([int(input()),True])
for i in range(H):
	Lines.append([int(input()),False])

Lines.sort()
X = Y = 0
ans = 0
for c,xy in Lines:
	if xy:
		ans += c*(H+1-Y)
		X += 1
	else:
		ans += c*(W+1-X)
		Y += 1

print(ans)

Submission status: Accepted

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:
    res += dic[1-x[1]]*x[0]
    dic[x[1]] -= 1

print(res)

Submission status: Accepted

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

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

p, q = sort(p), sort(q)

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

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[w] = maxsize
q[h] = maxsize
p, q = sort(p), sort(q)

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

Solution code:
w,h = map(int,input().split())
p = list(sorted([int(input()) for i in range(w)],reverse=True))
q = list(sorted([int(input()) for i in range(h)],reverse=True))

steps = w+h
w += 1; h += 1
ret = 0
for i in range(steps):
    if w == 1 or h != 1 and p[-1] > q[-1]:
        ret += w * q.pop()
        h -= 1
    else:
        ret += h * p.pop()
        w -= 1
print(ret)

Submission status: Accepted

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 = 0
    pi = 0
    qi = 0
    for i in range(w+h):
        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: Accepted

Solution code:
import heapq

pq = []
# 

W, H = map(int, input().split())
for i in range(W):
	heapq.heappush(pq, (int(input()), 'W'))
for i in range(H):
	heapq.heappush(pq, (int(input()), 'H'))

W += 1
H += 1

ans = 0
while pq:
	(num, dire) = heapq.heappop(pq)
	if dire == 'W':
		ans += num * H
		W -= 1
	else:
		ans += num * W
		H -= 1

print(ans)

Submission status: Accepted

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

Solution code:
W, H = map(int, raw_input().split())
 
p_list = list()
q_list = list()
 
for i in range(W):
    p_list.append(int(raw_input()))
    
for j in range(H):
    q_list.append(int(raw_input()))
 
p_list.sort()
q_list.sort()
 
cp = H+1
cq = W+1
 
res = 0
pid = 0
qid = 0
 
while True:
    if pid == W:
        if qid == H:
            break
        else:
            choice = 'q'
    elif qid == H:
        choice = 'p'
    elif p_list[pid] < q_list[qid]:
        choice = 'p'
    else:
        choice = 'q'
    if choice == 'p':
        cq -= 1
        res += cp*p_list[pid]
        pid += 1
    else:
        cp -= 1
        res += cq*q_list[qid]
        qid += 1
 
print res

Submission status: Accepted

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

from __future__ import division, print_function, absolute_import, unicode_literals

W, H = map(int, input().split())
cx = 0
cy = 0
P = [(i, int(input()), 'W') for i in range(W)]
Q = [(i, int(input()), 'H') for i in range(H)]

PQ = sorted(P+Q, key=lambda x: x[1])
ans = 0
for index, cost, wh in PQ:
    if wh == 'W':
        cx += 1
        ans += cost * (H + 1 - cy)
    elif wh == 'H':
        cy += 1
        ans += cost * (W + 1 - cx)
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)]

P.sort()
Q.sort()

ans = 0
for p in P:
    ind = bisect.bisect_right(Q, p)
    ans += p * (H - ind + 1)
for q in Q:
    ind = bisect.bisect_left(P, q)
    ans += q * (W - ind + 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
W, H = map(int, input().split())
pandq = []
for i in range(W):
	pandq.append([int(input()),"p"])
for i in range(H):
	pandq.append([int(input()),"q"])
sortedCost = deque(sorted(pandq))

a = W + 1
b = H + 1
totalcosts = 0
while sortedCost:
	cost = sortedCost.popleft()
	if cost[1] == "p":
		totalcosts += cost[0] * b
		a -= 1
	else:
		totalcosts += cost[0] * a
		b -= 1
print(totalcosts)

Submission status: Accepted

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

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

def r(xy):
    if xy == 0:
        return 1
    return 0

WH = (W + 1, H + 1)
C = [0, 0]
answer = 0
for w, xy in edges:
    C[xy] += 1
    n = WH[r(xy)] - C[r(xy)]
    answer += n * w
print(answer)

Submission status: Accepted

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

p_list = list()
q_list = list()

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

p_list.sort()
q_list.sort()

cp = H+1
cq = W+1

res = 0
pid = 0
qid = 0

while True:
    if pid == W:
        if qid == H:
            break
        else:
            choice = 'q'
    elif qid == H:
        choice = 'p'
    elif p_list[pid] < q_list[qid]:
        choice = 'p'
    else:
        choice = 'q'
    if choice == 'p':
        cq -= 1
        res += cp*p_list[pid]
        pid += 1
    else:
        cp -= 1
        res += cq*q_list[qid]
        qid += 1

print res

Submission status: Accepted

Solution code:
w,h=map(int,raw_input().split())
p=[[int(raw_input()),0] for _ in xrange(w)]
q=[[int(raw_input()),1] for _ in xrange(h)]
pq=p+q
pq.sort()
a=w+1
b=h+1
ans=0
for i in xrange(w+h):
    if pq[i][1]==0:
        ans+=b*pq[i][0]
        a-=1
    else:
        ans+=a*pq[i][0]
        b-=1

print(ans)

Submission status: Accepted

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

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

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

    pi = w-1
    qi = h-1
    res = 0
    while 0<=pi and 0<=qi:
        if p[pi] < q[qi]:
            res += p[pi] * (h+1)
            pi -= 1
            w -= 1
        else:
            res += q[qi] * (w+1)
            qi -= 1
            h -= 1
    res += sum(p[:pi+1]) + sum(q[:qi+1])
    print(res)

main()

Submission status: Accepted

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)
 

cnt = W*H

WW = H
HH = W



pin = 0
qin = 0


while cnt:

    if PI[pin] > QI[qin]:
        ans -= PI[pin] * WW
        HH-=1
        cnt -= WW
        pin += 1
    else:
        ans -= QI[qin] * HH

        WW-=1
        cnt -= HH
        qin+=1
print ans

Submission status: Accepted

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

wl = w
hl = h

cost = 0

p.sort()
q.sort()

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

pc = 0
qc = 0

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

print cost

Submission status: Accepted

Solution code:
ss=raw_input().split()
w=int(ss[0])
h=int(ss[1])

a=[]
b=[]

for i in xrange(w):
    p=input()
    a.append(p)
for i in range(h):
    p=input()
    b.append(p)

a.sort()
b.sort()

h1=0
h2=0
res=0

while h1 < w and h2 < h:
    if a[h1]<b[h2]:
        res += a[h1] * (h - h2 + 1)
        h1 += 1
    else:
        res += b[h2] * (w - h1 + 1)
        h2 += 1
while (h1<w):
    res += a[h1]
    h1 += 1
while (h2<h):
    res += b[h2]
    h2 += 1
print res

Submission status: Accepted

Solution code:

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

print cost

Submission status: Accepted

Solution code:
ss=raw_input().split()
w=int(ss[0])
h=int(ss[1])
a=[]
b=[]
for i in range( w):
    p=input()
    a.append( p)
for i in range( h):
    p=input()
    b.append( p)
a.sort()
b.sort()
h1=0
h2=0
ans=0
while ((h1<w) and (h2<h)):
    if a[h1]<b[h2]:
        ans+=a[h1]*(h - h2+1)
        h1+=1
    else :
        ans += b[h2] * (w-h1+1)
        h2 += 1
while (h1<w):
    ans+=a[h1]
    h1+=1
while (h2<h):
    ans+=b[h2]
    h2+=1
print ans

Submission status: Accepted

Solution code:
ss=raw_input().split()
w=int(ss[0])
h=int(ss[1])
a=[]
b=[]
for i in range(w):
    p=input()
    a.append(p)
for i in range(h):
    p=input()
    b.append(p)
a.sort()
b.sort()
h1=0
h2=0
ans=0
while ((h1<w) and (h2<h)):
    if a[h1]<b[h2]:
        ans+=a[h1]*(h - h2+1)
        h1+=1
    else :
        ans += b[h2] * (w-h1+1)
        h2 += 1
while (h1<w):
    ans+=a[h1]
    h1+=1
while (h2<h):
    ans+=b[h2]
    h2+=1
print ans

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np
w, h = map(int, input().split())
ps = [int(input()) for _ in range(w)]
qs = np.sort([int(input()) for _ in range(h)])
sqs = np.cumsum(qs)
bound = np.searchsorted(qs, ps)

s = sum(qs) + sum(ps)

for p, b in zip(ps, bound):
    if b > 0:
        s += sqs[b-1] + p*(h-b)
    else:
        s += p*h

print(s)

Submission status: Accepted

Solution code:
W, H = map(int, raw_input().split())
p = sorted([(i, int(raw_input())) for i in xrange(W)], key=lambda x:-x[1])
q = sorted([(i, int(raw_input())) for i in xrange(H)], key=lambda x:-x[1])
ans = 0
pe, qe, ae = 0, 0, (W+1)*(H+1)-1
while len(p)> 0 or len(q) > 0:
    if len(q) == 0 or (len(p) > 0 and p[-1][1] <= q[-1][1]):
        i, cost = p.pop()
        pe += 1
        ans += cost*(H+1-qe)
    else:
        j, cost = q.pop()
        qe += 1
        ans += cost*(W+1-pe)

print ans

Submission status: Accepted

Solution code:
#import heapq



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





is_connected_X = [False for _ in range(W)]
count_connected_X = 0
is_connected_Y = [False for _ in range(H)]
count_connected_Y=0

P = [(i,int(input()),"W") for i in range(W)]
Q = [(j,int(input()),"H") for j in range(H)]

PQ = sorted(P+Q, key=lambda x:x[1])

total_cost=0
for i,cost,wh in PQ:

    if wh=="W":
        count_connected_X+=1
        is_connected_X[i]=True
        total_cost+= cost*(H+1-count_connected_Y)
    elif wh=="H":
        count_connected_Y += 1
        is_connected_Y[i] = True
        total_cost += cost * (W + 1 - count_connected_X)

print(total_cost)

Submission status: Accepted

Solution code:
W, H = list(map(int, input().split()))
p = sorted([int(input()) for _ in range(W)], reverse=True)
q = sorted([int(input()) for _ in range(H)], reverse=True)
ans = 0
while len(p) > 0 and len(q) > 0:
    #print("p:{}, q:{}, ({},{})".format(p[-1], q[-1], W, H))
    if p[-1] < q[-1]:
        ans += p[-1] * (H + 1)
        #print("ans += {} * {} -> {}".format(p[-1], H+1, p[-1] * (H+1)))
        p.pop()
        W -= 1
    else:
        ans += q[-1] * (W + 1)
        #print("ans += {} * {} -> {}".format(q[-1], W+1, q[-1] * (W+1)))
        q.pop()
        H -= 1
ans += sum(p) + sum(q)
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

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

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

cost = sum(pw) * (h + 1) + sum(ph) * (w + 1)

phc = sorted(ph)
pwc = sorted(pw)

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

for i in range(h):
    index = bisect.bisect_right(pwc, ph[i])
    cost -= ph[i] * index

print cost