Submission #5913701

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef pair<long long, int> pp;
const int maxn = 200100;
const long long oo = 1e18;
int n;
long long a[maxn], b[maxn];
pp c[maxn];
bool flag[maxn] = {0};
long long ans;
int main()
{
std::ios::sync_with_stdio(false);
cin >> n;
long long suma = 0, sumb = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i] >> b[i];
c[i].first = a[i];
suma += a[i];
c[i].second = i;
c[i + n].first = b[i];
sumb += b[i];
c[i + n].second = i + n;
}
ans = min(suma, sumb);
sort(c + 1, c + n * 2 + 1);
long long sum = 0;
for(int i = 1; i <= n; i ++)
{
sum += c[i].first;
flag[c[i].second] = 1;
//cout << c[i].first << " " << c[i].second << endl;
}
/*
for(int i = 1; i <= n * 2; i ++)
if(flag[i])
cout << i << " " ;
cout << endl;
cout << "sum : " << sum << endl;
*/
for(int i = 1; i <= n; i ++)
{
if(flag[i] && flag[i + n])
{
cout << sum << endl;
return 0;
}
if(flag[i])
{
if(c[n].second != i)
{
ans = min(ans, sum - c[n].first + b[i]);
//cout << "asd1 " << c[n].first << " " << b[i] << endl;
}
else
{
ans = min(ans, sum - c[n - 1].first + b[i]);
//cout << "asd2 " << c[n - 1].first << " " << b[i] << endl;
}
}
else if(flag[i + n])
{
if(c[n].second != i + n)
{
ans = min(ans, sum - c[n].first + a[i]);
//cout << "asd3 " << c[n].first << " " << a[i] << endl;
}
else
{
ans = min(ans, sum - c[n - 1].first + a[i]);
//cout << "asd4 " << c[n - 1].first << " " << a[i] << endl;
}
}
else
ans = min(ans, sum - c[n].first - c[n - 1].first + a[i] + b[i]);
}
cout << ans << endl;
return 0;
}```

#### Submission Info

Submission Time 2019-06-15 15:18:24+0900 C - Min Cost Cycle zhangyuxi C++14 (GCC 5.4.1) 700 1848 Byte AC 38 ms 6400 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
sample-01.txt 2 ms 4352 KB
sample-02.txt 2 ms 4352 KB
sample-03.txt 2 ms 4352 KB