Problem:


Score : 700 points

Problem Statement

We have a directed weighted graph with N vertices.
Each vertex has two integers written on it, and the integers written on Vertex i are A_i and B_i.

In this graph, there is an edge from Vertex x to Vertex y for all pairs 1 \leq x,y \leq N, and its weight is {\rm min}(A_x,B_y).

We will consider a directed cycle in this graph that visits every vertex exactly once.
Find the minimum total weight of the edges in such a cycle.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

1 \leq B_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the minimum total weight of the edges in such a cycle.

Sample Input 1

3
1 5
4 2
6 3

Sample Output 1

7

Consider the cycle 1→3→2→1. The weights of those edges are {\rm min}(A_1,B_3)=1, {\rm min}(A_3,B_2)=2 and {\rm min}(A_2,B_1)=4, for a total of 7.
As there is no cycle with a total weight of less than 7, the answer is 7.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

10

Sample Input 3

6
19 92
64 64
78 48
57 33
73 6
95 73

Sample Output 3

227



Sample input:
3
1 5
4 2
6 3


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:
def mincos(n,ab):
    aball=[]
    aball+=[(ab[i][0],i+1,'a') for i in range(n)]
    aball+=[(ab[i][1],i+1,'b') for i in range(n)]
    aball.sort()
    
    ans1=sum([i[0] for i in aball[:n]])
    
    hen=aball[n][0]
    hen2=aball[n+1][0]
    d=[]
    t=None
    hantei=True
    for i,c,mab in aball[:n]:
        if t!=None and t!=mab:
            hantei=False
        if  c in d:
            print(ans1)
            exit()
        d+=[c]
        t=mab

    if hantei:
        print(ans1)
        exit()

    ans2=[]
    for i,c,aorb in aball[:n]:
        if aball[n][1]!=c:
            ans2+=[ans1-i+hen]
        else:
            ans2+=[ans1-i+hen2]
    print(min(ans2))
    exit()

n=int(input())
print(mincos(n,[list(map(int,input().split())) for i in range(n)]))

Submission status: Time Limit Exceeded

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

"""
AGC028 C
"""

from operator import itemgetter

n = int(input())
abli = []
for i in range(n):
    a, b = map(int, input().split())
    abli.append((a, i, 0))
    abli.append((b, i, 1))

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0),abli[:n]))

alist = []
blist = []
for x, i, aorb in abli[:n]:
    if not aorb:
        alist.append(i)
    else:
        blist.append(i)
 
flag = False
for i in range(n):
    if i in alist and i in blist:
        flag = True
        break
"""
abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])
"""

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 10**16
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum([a for a,i,aorb in abli if not aorb])
rightsum = sum([b for b,i,aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))

Submission status: Time Limit Exceeded

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

"""
AGC028 C
"""

from operator import itemgetter

n = int(input())
abli = []
for i in range(n):
    a, b = map(int, input().split())
    abli.append((a, i, 0))
    abli.append((b, i, 1))


abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 10**16
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum([a for a,i,aorb in abli if not aorb])
rightsum = sum([b for b,i,aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))

Submission status: Time Limit Exceeded

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

"""
AGC028 C
"""

import itertools
from operator import itemgetter

n = int(input())
abli0 = [tuple(map(int, input().split())) for i in range(n)]
eabli0 = enumerate(abli0)
abli1 = list(map(lambda t: ((t[1][0], t[0], 0), (t[1][1], t[0], 1)), eabli0))
abli = list(itertools.chain.from_iterable(abli1))
abli.sort(key=itemgetter(0))
tmpans0 = sum(map(lambda t: t[0], abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 2**62
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum(map(lambda x: x[0], abli0))
rightsum = sum(map(lambda x: x[1], abli0))

print(min(leftsum, rightsum, tmpans))

Submission status: Time Limit Exceeded

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

"""
AGC028 C
"""

import itertools

n = int(input())
abli0 = [tuple(map(int, input().split())) for i in range(n)]
eabli0 = enumerate(abli0)
abli1 = list(map(lambda t: ((t[1][0], t[0], 0), (t[1][1], t[0], 1)), eabli0))
abli = list(itertools.chain.from_iterable(abli1))
abli.sort(key=lambda t: t[0])
tmpans0 = sum(map(lambda t: t[0], abli[:n]))
alist = []
blist = []
for x, i, aorb in abli[:n]:
    if not aorb:
        alist.append(i)
    else:
        blist.append(i)

flag = False
for i in range(n):
    if i in alist and i in blist:
        flag = True
        break

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 2**62
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum(map(lambda x: x[0], abli0))
rightsum = sum(map(lambda x: x[1], abli0))

print(min(leftsum, rightsum, tmpans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
li= []
for i in range(n):
    li.append(list(map(int,input().split())))
a1 = list(itertools.permutations(range(n)))
min1 = float('inf')
for i in a1:
    if i[n-1] != 0:
        continue
    listi = list(i)
    listi.insert(0,0)
    aa = 0
    for j in range(len(listi)-1):
        aa += min(li[listi[j]][0],li[listi[j+1]][1])
    if aa < min1:
        min1 = aa
print(min1)

Submission status: Time Limit Exceeded

Solution code:
# -*- encoding: utf-8 -*-
SCORE_NONE = -1

class Life(object):
      """个体类"""
      def __init__(self, aGene = None):
            self.gene = aGene
            self.score = SCORE_NONE

import random

class GA(object):
      """遗传算法类"""
      def __init__(self, aCrossRate, aMutationRage, aLifeCount, aGeneLenght, aMatchFun = lambda life : 1):
            self.croessRate = aCrossRate
            self.mutationRate = aMutationRage
            self.lifeCount = aLifeCount
            self.geneLenght = aGeneLenght
            self.matchFun = aMatchFun                 # 适配函数
            self.lives = []                           # 种群
            self.best = None                          # 保存这一代中最好的个体
            self.generation = 1
            self.crossCount = 0
            self.mutationCount = 0
            self.bounds = 0.0                         # 适配值之和，用于选择是计算概率

            self.initPopulation()


      def initPopulation(self):
            """初始化种群"""
            self.lives = []
            for i in range(self.lifeCount):
                  gene = [ x for x in range(self.geneLenght) ] 
                  random.shuffle(gene)
                  life = Life(gene)
                  self.lives.append(life)


      def judge(self):
            """评估，计算每一个个体的适配值"""
            self.bounds = 0.0
            self.best = self.lives[0]
            for life in self.lives:
                  life.score = self.matchFun(life)
                  self.bounds += life.score
                  if self.best.score < life.score:
                        self.best = life


      def cross(self, parent1, parent2):
            """交叉"""
            index1 = random.randint(0, self.geneLenght - 1)
            index2 = random.randint(index1, self.geneLenght - 1)
            tempGene = parent2.gene[index1:index2]   # 交叉的基因片段
            newGene = []
            p1len = 0
            for g in parent1.gene:
                  if p1len == index1:
                        newGene.extend(tempGene)     # 插入基因片段
                        p1len += 1
                  if g not in tempGene:
                        newGene.append(g)
                        p1len += 1
            self.crossCount += 1
            return newGene


      def  mutation(self, gene):
            """突变"""
            index1 = random.randint(0, self.geneLenght - 1)
            index2 = random.randint(0, self.geneLenght - 1)

            newGene = gene[:]       # 产生一个新的基因序列，以免变异的时候影响父种群
            newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
            self.mutationCount += 1
            return newGene


      def getOne(self):
            """选择一个个体"""
            r = random.uniform(0, self.bounds)
            for life in self.lives:
                  r -= life.score
                  if r <= 0:
                        return life

            raise Exception("选择错误", self.bounds)


      def newChild(self):
            """产生新后的"""
            parent1 = self.getOne()
            rate = random.random()

            # 按概率交叉
            if rate < self.croessRate:
                  # 交叉
                  parent2 = self.getOne()
                  gene = self.cross(parent1, parent2)
            else:
                  gene = parent1.gene

            # 按概率突变
            rate = random.random()
            if rate < self.mutationRate:
                  gene = self.mutation(gene)

            return Life(gene)


      def next(self):
            """产生下一代"""
            self.judge()
            newLives = []
            newLives.append(self.best)            #把最好的个体加入下一代
            while len(newLives) < self.lifeCount:
                  newLives.append(self.newChild())
            self.lives = newLives
            self.generation += 1
		

import math

class TSP(object):
      def __init__(self, aLifeCount = 100,):
            self.initCitys()
            self.lifeCount = aLifeCount
            self.ga = GA(aCrossRate = 0.7, 
                  aMutationRage = 0.02, 
                  aLifeCount = self.lifeCount, 
                  aGeneLenght = len(self.citys), 
                  aMatchFun = self.matchFun())


      def initCitys(self):
            self.citys = []
            n=int(input())
            for i in range(0,n):
                a,b=map(int,input().split())
                self.citys.append((a,b))
            
      def distance(self, order):
            distance = 0
            for i in range(-1, len(self.citys) - 1):
                  index1, index2 = order[i], order[i + 1]
                  city1, city2 = self.citys[index1], self.citys[index2]
                  distance+=min(city1[0],city2[1])

                  """
                  R = 6371.004
                  Pi = math.pi 
                  LatA = city1[1]
                  LatB = city2[1]
                  MLonA = city1[0]
                  MLonB = city2[0]
                  C = math.sin(LatA*Pi / 180) * math.sin(LatB * Pi / 180) + math.cos(LatA * Pi / 180) * math.cos(LatB * Pi / 180) * math.cos((MLonA - MLonB) * Pi / 180)
                  D = R * math.acos(C) * Pi / 100
                  distance += D
                  """
            return distance


      def matchFun(self):
            return lambda life: 1.0 / self.distance(life.gene)


      def run(self, n = 0):
            while n > 0:
                  self.ga.next()
                  distance = self.distance(self.ga.best.gene)
                  #print (("%d : %f") % (self.ga.generation, distance))
                  n -= 1
            print(distance)


def main():
      tsp = TSP()
      tsp.run(100)


if __name__ == '__main__':
      main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = [[10 ** 9 + 1, 0, 0] for i in range(N + 1)]
for i in range(N):
  a, b = map(int, input().split())
  AB.append([a, i, 0])
  AB.append([b, i, 1])
  AB.sort()
  AB = AB[:N + 1]
ans = sum([ab[0] for ab in AB])
A = []
B = []
C = []
AB.sort(key=lambda x: x[1])
while AB:
  if len(AB) > 1 and AB[0][1] == AB[1][1]:
    if AB[0][2] == 0:
      C.append([AB[0][0], AB[1][0]])
    else:
      C.append([AB[1][0], AB[0][0]])
    AB = AB[2:]
  elif AB[0][2] == 0:
    A.append(AB[0][0])
    AB = AB[1:]
  else:
    B.append(AB[0][0])
    AB = AB[1:]
if len(A) == 0:
  ans -= max(max(B), max([c[0] for c in C]))
elif len(B) == 0:
  ans -= max(max(A), max([c[1] for c in C]))
elif len(C) == 1:
  ans -= max(max(A), max(B))
else:
  ans -= max(max(A), max(B), max([max(c) for c in C]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = [0] * 2 * N
for i in range(N):
  a, b = map(int, input().split())
  AB[2 * i] = [a, i, 0]
  AB[2 * i + 1] = [b, i, 1]
AB.sort()
AB = AB[:N+1]
ans = sum([ab[0] for ab in AB])
A = []
B = []
C = []
AB.sort(key=lambda x: x[1])
while AB:
  if len(AB) > 1 and AB[0][1] == AB[1][1]:
    if AB[0][2] == 0:
      C.append([AB[0][0], AB[1][0]])
    else:
      C.append([AB[1][0], AB[0][0]])
    AB = AB[2:]
  elif AB[0][2] == 0:
    A.append(AB[0][0])
    AB = AB[1:]
  else:
    B.append(AB[0][0])
    AB = AB[1:]
if len(A) == 0:
  ans -= max(max(B), max([c[0] for c in C]))
elif len(B) == 0:
  ans -= max(max(A), max([c[1] for c in C]))
elif len(C) == 1:
  ans -= max(max(A), max(B))
else:
  ans -= max(max(A), max(B), max([max(c) for c in C]))
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.buffer.readline())
AB = list(map(int, sys.stdin.buffer.read().split()))
A = AB[::2]
B = AB[1::2]
ans = min(sum(A), sum(B))
AB.sort()
pivot = AB[N-1]
pivot2 = AB[N]
pivot_idxs = []
pivot2_idxs = []
ans2 = sum(AB[:N])
for i, (a, b) in enumerate(zip(A, B)):
    if a <= pivot and b <= pivot:
        ans = min(ans, ans2)
        print(ans)
        exit()
    if a == pivot or b == pivot:
        pivot_idxs.append(i)
    if a == pivot2 or b == pivot2:
        pivot2_idxs.append(i)

if len(pivot_idxs) == len(pivot2_idxs) == 1 and pivot_idxs[0] == pivot2_idxs[0]:
    ans2 = min(
        ans2 - pivot + AB[N+1],
        ans2 - AB[N-2] + pivot2
    )
else:
    ans2 = ans2 - pivot + pivot2
ans = min(ans, ans2)
print(ans)

Submission status: Accepted

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


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]


sum_a = 0
sum_b = 0
for a, b in info:
    sum_a += a
    sum_b += b
ans = min(sum_a, sum_b)

res = []
for i in range(n):
    a, b = info[i]
    res.append(a)
    res.append(b)
res.sort()
min_half_sum = sum(res[0:n - 2])


for i in range(n):
    a, b = info[i]
    a, b = max(a, b), min(a, b)
    ind1 = bisect.bisect_right(res, a, lo=0, hi=2*n) - 1
    ind2 = bisect.bisect_right(res, b, lo=0, hi=ind1+1) - 1
    
    tmp_ans = min_half_sum
    cnt = 0
    if n - 2 <= ind1:
        tmp_ans += a
    else:
        cnt += 1
    if n - 2 <= ind2:
        tmp_ans += b
    else:
        cnt += 1

    for i in range(n - 2, 2 *n):
        if cnt == 0:
            break
        if i == ind1 or i == ind2:
            continue
        tmp_ans += res[i]
        cnt -= 1
    ans = min(tmp_ans, ans)

print(ans)

Submission status: Accepted

Solution code:
N=int(input());A=[-1]*N;B=[-1]*N
for i in range(N):A[i],B[i]=map(int,input().split())
ans=min(sum(A),sum(B));t=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)];t.sort();d=[0]*N
for i in range(N):d[t[i][1]]+=1
S=sum(t[i][0] for i in range(N))
if max(d)==2:
    print(S)
else:
    ans2=min(S+max(A[i],B[i])-t[N-1-(t[N-1][1]==i)][0] for i in range(N))
    print(min(ans,ans2))

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline;N=int(input());A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
ans=min(sum(A),sum(B));temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)];temp.sort();data=[0]*N
for i in range(N):data[temp[i][1]]+=1
S=sum(temp[i][0] for i in range(N))
if max(data)==2:
    print(S)
else:
    for i in range(N):ans=min(ans,S+max(A[i],B[i])-temp[N-1-(temp[N-1][1]==i)][0]);
    print(ans)

Submission status: Accepted

Solution code:
import sys,random

input=sys.stdin.readline

N=int(input())
A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())

ans=min(sum(A),sum(B))

temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)]
temp.sort()
#print(temp)
data=[0]*N
for i in range(N):
    val,id=temp[i]
    data[id]+=1
S=sum(temp[i][0] for i in range(N))

for i in range(N):
    if data[i]==2:
        test=S
        ans=min(ans,test)
    elif data[i]==1:
        if temp[N-1][1]!=i:
            test=S+max(A[i],B[i])-temp[N-1][0]
        else:
            test=S+max(A[i],B[i])-temp[N-2][0]
        ans=min(ans,test)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]
both = []
for i in range(n):
  both.extend(ab[i])
both.sort()
ans = 10**18
sm = sum(both[:n])
for i in range(n):
  ai = bisect.bisect_left(both,ab[i][0])
  bi = bisect.bisect_left(both,ab[i][1])
  if ai < n and bi < n:
    ans = min(ans,sm)
  elif ai < n-1:
    ans = min(ans,sm-both[n-1]+ab[i][1])
  elif ai == n-1:
    ans = min(ans,sm-both[n-2]+ab[i][1])
  elif bi < n-1:
    ans = min(ans,sm-both[n-1]+ab[i][0])
  elif bi == n-1:
    ans = min(ans,sm-both[n-2]+ab[i][0])
  else:
    ans = min(ans,sm-both[n-1]-both[n-2]+sum(ab[i]))
a,b = list(zip(*ab))
ans = min(ans,sum(a),sum(b))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

edge = []
num_list = []

for i in range(n):
    a, b = map(int, input().split())
    edge.append([a, b])
    num_list.append(a)
    num_list.append(b)

num_list.sort()
K = num_list[n-1]

ab = []
ax = []
xb = []

for i in range(n):
    a, b = edge[i]
    if a <= K and b <= K:
        ab.append(edge[i])
    elif a <= K:
        ax.append(edge[i])
    elif b <= K:
        xb.append(edge[i])

if len(ab) > 0:
    ans = sum(num_list[:n])
elif len(ax) == n or len(xb) == n:
    ans = sum(num_list[:n])
else:
    yabai_edge = num_list[n-1:n+1]
    if edge.count(yabai_edge) + edge.count(yabai_edge[::-1]) == 0:
        diff = num_list[n] - num_list[n-1]
    elif len(ax) == 1 and edge.count(yabai_edge) == 1:
        diff = num_list[n] - num_list[n-1]
    elif len(xb) == 1 and edge.count(yabai_edge[::-1]) == 1:
        diff = num_list[n] - num_list[n-1]
    else:
        diff = min(num_list[n+1]-num_list[n-1], num_list[n]-num_list[n-2]) 
    ans = sum(num_list[:n]) + diff

print(ans)

Submission status: Accepted

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

N = int(readline())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
A, B = map(list, zip(*AB))

ans = min(sum(A), sum(B))
C = [(A[i], i) for i in range(N)] + [(B[i], i) for i in range(N)]

C.sort()

table = [0]*N
for i in range(N):
    _, idx = C[i]
    table[idx] += 1
if max(table) > 1:
    ans = min(ans, sum(c for (c, _) in C[:N]))

else:
    MAB = list(map(max, AB))
    D = [None]*N
    for i in range(N, 2*N):
        _, idx = C[i]
        D[idx] = i
    
    res = sum(c for (c, _) in C[:N])
    for i in range(N-1):
        _, idx = C[i]
        ans = min(ans, res + MAB[idx] - C[N-1][0])
    ans = min(ans, res + MAB[C[N-1][1]] - C[N-2][0])

print(ans)

Submission status: Accepted

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

n=int(input())
A=[]

A1=0
B1=0

for i in range(n):
    a,b=map(int,input().split())
    
    A1+=a
    B1+=b
    
    A.append((a,2*i))
    A.append((b,2*i+1))


ANS=min(A1,B1)

A.sort()
INVIND=[-1]*(2*n)

for ind,(a,i) in enumerate(A):
    INVIND[i]=ind

S=[0]

for a,i in A:
    S.append(S[-1]+a)


for i in range(n):
    if INVIND[i*2]<n and INVIND[i*2+1]<n:
        ANS=min(ANS,S[n])

    elif INVIND[i*2]<n-1 and INVIND[i*2+1]>=n-1:
        ANS=min(ANS,A[INVIND[i*2+1]][0]+S[n-1])

    elif INVIND[i*2]>=n-1 and INVIND[i*2+1]<n-1:
        ANS=min(ANS,A[INVIND[i*2]][0]+S[n-1])

    else:
        ANS=min(ANS,S[n-2]+A[INVIND[i*2]][0]+A[INVIND[i*2+1]][0])

    #print(i,ANS)

print(ANS)

Submission status: Accepted

Solution code:
N = int(input())
D = []
for i in range(N):
    a, b = map(int, input().split())
    D.append((a, 0, i))
    D.append((b, 1, i))

D.sort()
ans = 0
C = [False] * N
db = False
gr = [0] * 2
for i in range(N):
    ans += D[i][0]
    gr[D[i][1]] += 1
    if C[D[i][2]]:
        db = True
    C[D[i][2]] = True

if not db and gr[0] != 0 and gr[1] != 0:
    if D[N - 1][2] == D[N][2]:
        ans = min(ans - D[N - 2][0] + D[N][0], ans - D[N - 1][0] + D[N + 1][0])
    else:
        ans = ans - D[N - 1][0] + D[N][0]

print(ans)

Submission status: Accepted

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

import numpy as np

"""
各辺に対して、Ax,Byの好きな方をとれるとしてよい
全部で半分ずつ → たいてい実現可能

・全部ox
・全部xo
・xx,ooともに存在→ひとつ oo で決め打てば、貪欲に半分とれる
"""

N = int(input())
AB = np.array([[int(x) for x in input().split()] for _ in range(N)],dtype=np.int64)

answer = AB[:,0].sum()
answer = min(answer,AB[:,1].sum())

AB.sort(axis=1)
A,B = AB.T
i = A.argsort()
A = A[i]; B = B[i]

if A.max() > B.min():
    # 全体から貪欲にN個
    C = np.concatenate([A,B])
    C.sort()
    answer = min(answer, C[:N].sum())

# 全体から両取りを1つ
x = A[:-1].sum() + B[:-1].min()
y = A[-1]+B[-1] + A[:-2].sum()
answer = min(answer,x,y)

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
As, Bs = [], []
for i in range(N):
    A, B = map(int, input().split())
    As.append((A, i))
    Bs.append((B, i))

ansA = sum([A for A, i in As])
ansB = sum([B for B, i in Bs])

Cs = sorted(As + Bs)

useds = [False] * N
sumC = 0
for C, i in Cs[:N]:
    useds[i] = True
    sumC += C

if not all(useds):
    ansC = sumC
elif Cs[N-1][1] != Cs[N][1]:
    ansC = sumC - Cs[N-1][0] + Cs[N][0]
else:
    ansC = min(sumC - Cs[N-2][0] + Cs[N][0], sumC - Cs[N-1][0] + Cs[N+1][0])

print(min(ansA, ansB, ansC))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
A=0
B=0
table=[]
for i in range(N):
    a,b=map(int,input().split())
    table.append((a,i))
    table.append((b,i))
    A+=a
    B+=b
ans=min(A,B)
table.sort()
num=0
for i in range(N):
    num+=table[i][0]
L=[0]*N
#print(table)
for i in range(N):
    c,j=table[i]
    if L[j]!=0:
        ans=min(num,ans)
        print(ans)
        #print(L)
        sys.exit()
    L[j]+=1
c,n=table[N-1]
if n!=table[N][1]:
    num=num-table[N-1][0]+table[N][0]
    ans = min(num, ans)
    print(ans)
    sys.exit()
num1=num-table[N-1][0]+table[N+1][0]
num2=num-table[N-2][0]+table[N][0]
print(min(ans,num1,num2))

Submission status: Accepted

Solution code:
import sys
N=int(input())
A=0
B=0
table=[]
for i in range(N):
    a,b=map(int,input().split())
    table.append((a,i))
    table.append((b,i))
    A+=a
    B+=b
ans=min(A,B)
table.sort()
num=0
for i in range(N):
    num+=table[i][0]
L=[0]*N
#print(table)
for i in range(N):
    c,j=table[i]
    if L[j]!=0:
        ans=min(num,ans)
        print(ans)
        #print(L)
        sys.exit()
    L[j]+=1
c,n=table[N-1]
if n!=table[N][1]:
    num=num-table[N-1][0]+table[N][0]
    ans = min(num, ans)
    print(ans)
    sys.exit()
num1=num-table[N-1][0]+table[N+1][0]
num2=num-table[N-2][0]+table[N][0]
print(min(ans,num1,num2))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
Cost=[]
s1,s2=0,0
for i in range(n):
    a,b=map(int,input().split())
    s1+=a
    s2+=b
    Cost.append([a,i])
    Cost.append([b,i])
Cost.sort()
s3=sum([Cost[i][0] for i in range(n)])
if len(set([Cost[i][1] for i in range(n)]))==n:
    if Cost[n-1][1]==Cost[n][1]:
        s3+=min(Cost[n+1][0]-Cost[n-1][0],Cost[n][0]-Cost[n-2][0])
    else:
        s3+=Cost[n][0]-Cost[n-1][0]
print(min(s1,s2,s3))

Submission status: Accepted

Solution code:
def mincos(n,ab):
    aball=[]
    aball+=[(ab[i][0],i+1,'a') for i in range(n)]
    aball+=[(ab[i][1],i+1,'b') for i in range(n)]
    aball.sort()
    
    ans1=sum([i[0] for i in aball[:n]])

    hen=aball[n][0]
    hen2=aball[n+1][0]
    d=set()
    t=None
    hantei=True
    for i,c,mab in aball[:n]:
        if t!=None and t!=mab:
            hantei=False
        if  c in d:
            print(ans1)
            exit()
        d.add(c)
        t=mab

    if hantei:
        print(ans1)
        exit()

    ans2=[]
    for i,c,aorb in aball[:n]:
        if aball[n][1]!=c:
            ans2+=[ans1-i+hen]
        else:
            ans2+=[ans1-i+hen2]
    print(min(ans2))
    exit()

n=int(input())
print(mincos(n,[list(map(int,input().split())) for i in range(n)]))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
node=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,i,"left"))
  A.append((y,i,"right"))
  node.append((x,y))
  
A.sort()
Used=[[False,False] for i in range(N)]
Used_node=0
for i in range(N):
  if A[i][2]=="left":
    Used[A[i][1]][0]=True
    if not Used[A[i][1]][1]:
      Used_node+=1
  if A[i][2]=="right":
    Used[A[i][1]][1]=True
    if not Used[A[i][1]][0]:
      Used_node+=1
if Used_node!=N:
  ans=0
  for i in range(N):
    ans+=A[i][0]
  print(ans)
else:
  if Used[0][0]:
    f=0
  else:
    f=1
  NO=0
  for i in range(N):
    if not Used[i][f]:
      NO=1
      break
  ans=0
  for i in range(N):
    ans+=A[i][0]
  ans2=float("inf")
  if NO==1:
    for w in range(N):
      if A[N][1]==w:
        ans2=min(ans2,ans-min(node[w])+A[N+1][0])
      else:
        ans2=min(ans2,ans-min(node[w])+A[N][0])
    print(ans2)
    exit()
  print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
Sa = 0
Sb = 0
for i in range(N):
    a,b = map(int,input().split())
    A.append([a,i])
    B.append([b,i])
    Sa += a
    Sb += b
C = sorted(A+B)
ind = []
ans = 0
for i in range(N):
    ind.append(C[i][1])
    ans += C[i][0]
ind = set(ind)
if len(ind) == N:
    if C[N-1][1] != C[N][1]:
        ans += C[N][0]-C[N-1][0]
    else:
        ans += min(C[N][0]-C[N-2][0],C[N+1][0]-C[N-1][0])
ans = min(Sa,Sb,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    test_case = 'c1.in'
    sys.stdin = open(test_case)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n = read_int()
    rows = [read_int_list() for i in range(n)]
    a, b = map(list, zip(*rows))
    res = sum(a)
    res = min(res, sum(b))
    all_values = [(a[i], i, 0) for i in range(n)]
    all_values.extend([(b[i], i, 1) for i in range(n)])
    all_values.sort()
    index_of_value = {v: i for i, v in enumerate(all_values)}
    first_values = [
        set(all_values[:n - 2]),
        set(all_values[:n - 1]),
        set(all_values[:n]),
    ]

    s = [sum([t[0] for t in v]) for v in first_values]
    for i in range(n):
        rest = []
        k = 0
        last = n - 2
        indices = sorted([(index_of_value[(a[i], i, 0)], a[i]),
                          (index_of_value[(b[i], i, 1)], b[i])])

        for index, value in indices:
            if index < last:
                last += 1
                k += 1
            else:
                rest.append(value)
        t = s[k] + sum(rest)
        res = min(res, t)
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
辺のコストをmin(Ax, By)とする代わりに、
辺のコストをAxもしくはByの好きな方にしてよいとしたときの最小値を求める

各頂点vについて、
１．Av, Bvともに選ばれる
２．Avのみ選ばれる
３．Bvのみ選ばれる
４．Av, Bvとも選ばれない

すべてタイプ2のときはsum(A), すべてタイプ3のときはsum(B)
それ以外は、タイプ1 = タイプ4 
2...2 4141..4 3...3 1
と構成すればよい
A, Bを合併したリストから小さい順にN個取る
この時に、最初のN個に同じ頂点由来のAv, Bvが両方含まれていたら上のように構成してしまえばよい
明らかにこれが最小値
含まれていないときは, 最初のn項についてそれぞれ取り除いたときにどうなるかを考える
Aw/Bwを取り除いたとすると, N+1番目の項がBw/AwでなければN+1番目の項を追加
Bw/Awの時はN+2番目の項を追加
（最初のN項が頂点について被りがないという条件から、これにより必ずあるvについてAv, Bv両方が含まれることになる
'''

n = int(input())
x = []
for i in range(n):
    ai, bi = map(int, input().split())
    x += [[i, ai, 0], [i, bi, 1]]
s1 = sum([x[2 * i][1] for i in range(n)])
s2 = sum([x[2 * i + 1][1] for i in range(n)])


x.sort(key = lambda x: x[1])
s3 = sum([x[i][1] for i in range(n)])
if len(set([x[i][0] for i in range(n)])) != n:
    print(min(s1, s2, s3))
else:
    if x[n - 1][0] == x[n][0]:
        s4 = min(s3 - x[n - 1][1] + x[n + 1][1], s3 - x[n - 2][1] + x[n][1])
    else:
        s4 = s3 - x[n - 1][1] + x[n][1]
    print(min(s1, s2, s4))

Submission status: Accepted

Solution code:
N = int(input())
import sys

all_list = []
counter = 1
for line in sys.stdin:
    a, b = [int(x) for x in line.strip().split(" ")]
    all_list += [("a", counter, a), ("b", counter, b)]
    counter += 1

all_list = sorted(all_list, key = lambda x : x[2])

sp_c = all_list[N][1]
sp_i_p = all_list[N][2]
sp_i_pp = all_list[N+1][2]

flag = True
ss = sum([i[2] for i in all_list[:N]])
d = set()
temp = None
for ab, c, i in all_list[:N]:
    if temp != None and temp != ab:
        flag = False
    if c in d:
        flag = True
        break
    d.add(c)
    temp = ab
if flag:
    print(ss)
else:
    candidates = []
    for ab, c, i in all_list[:N]:
        if sp_c != c:
            candidates.append(ss - i + sp_i_p)
        else:
            candidates.append(ss - i + sp_i_pp)
    print(min(candidates))

Submission status: Accepted

Solution code:
n = int(input())
b = []
ASUM = 0
BSUM = 0
for i in range(n):
  x,y = map(int,input().split())
  b.append([x,i])
  b.append([y,i])
  ASUM += x
  BSUM += y
a = sorted(b)
tuka = [0] * n
flag = 0
for i in range(n):
  if tuka[a[i][1]] == 1:
    flag = 1
    break
  else:
    tuka[a[i][1]] = 1
ans = 0
for i in range(n):
  ans += a[i][0]
if flag == 0:
  tmp = float("inf")
  las = a[n-1]
  bu = a[n-2]
  for i in range(n):
    if las[1] == i:
      tmp = min(tmp,max(b[i*2][0],b[i*2+1][0])-bu[0])
    else:
      tmp = min(tmp,max(b[i*2][0],b[i*2+1][0])-las[0])
  ans += tmp
ans = min(ans,ASUM,BSUM)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

suma = sumb = 0
elems = []
for i,(a,b) in enumerate(src):
    suma += a
    sumb += b
    elems.append((a,i))
    elems.append((b,i))
ans = min(suma, sumb)
elems.sort()

sumw = 0
used = [0]*N
dup = False
for w,i in elems[:N]:
    sumw += w
    used[i] += 1
    if used[i] > 1: dup = True

if dup:
    ans = min(ans, sumw)
    print(ans)
    exit()

for i,(a,b) in enumerate(src):
    if a > b:
        a,b = b,a
    neww = elems[N][0] if i != elems[N][1] else elems[N+1][0]
    tmp = sumw - a + neww
    ans = min(ans, tmp)
print(ans)