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
Task C - Min Cost Cycle
User zhangyuxi
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1848 Byte
Status
Exec Time 38 ms
Memory 6400 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 700 / 700 sample-01.txt, sample-02.txt, sample-03.txt, sample-01.txt, sample-02.txt, sample-03.txt, subtask01-01.txt, subtask01-02.txt, subtask01-03.txt, subtask01-04.txt, subtask01-05.txt, subtask01-06.txt, subtask01-07.txt, subtask01-08.txt, subtask01-09.txt, subtask01-10.txt, subtask01-11.txt, subtask01-12.txt, subtask01-13.txt, subtask01-14.txt, subtask01-15.txt, subtask01-16.txt, subtask01-17.txt, subtask01-18.txt, subtask01-19.txt, subtask01-20.txt, subtask01-21.txt, subtask01-22.txt, subtask01-23.txt, subtask01-24.txt, subtask01-25.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
subtask01-01.txt 2 ms 4352 KB
subtask01-02.txt 26 ms 6400 KB
subtask01-03.txt 35 ms 6272 KB
subtask01-04.txt 2 ms 4352 KB
subtask01-05.txt 25 ms 6272 KB
subtask01-06.txt 26 ms 6400 KB
subtask01-07.txt 35 ms 6272 KB
subtask01-08.txt 33 ms 6400 KB
subtask01-09.txt 24 ms 6272 KB
subtask01-10.txt 25 ms 6272 KB
subtask01-11.txt 30 ms 6272 KB
subtask01-12.txt 33 ms 6400 KB
subtask01-13.txt 19 ms 6016 KB
subtask01-14.txt 37 ms 6400 KB
subtask01-15.txt 37 ms 6272 KB
subtask01-16.txt 37 ms 6400 KB
subtask01-17.txt 38 ms 6400 KB
subtask01-18.txt 37 ms 6400 KB
subtask01-19.txt 37 ms 6272 KB
subtask01-20.txt 38 ms 6400 KB
subtask01-21.txt 37 ms 6400 KB
subtask01-22.txt 37 ms 6400 KB
subtask01-23.txt 36 ms 6272 KB
subtask01-24.txt 38 ms 6400 KB
subtask01-25.txt 37 ms 6400 KB