Submission #3399343


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
typedef pair<int, int> P;

#define frep(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) frep(i, 0, (n))
#define rrep(i, n) for(int i = (n - 1); i >= 0; i--)
#define all(i, x) for(typeof(x.begin()) i = x.begin(); i != x.end(); i++)
#define pb push_back

const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int MAX = 100010;
const int INF = 1e9;
const int MOD = 1000000007;
const string END = "\n";

void solve(){
	int n; cin >> n;
	vector<P> a, b;
	rep(i, n){
		int s, t; cin >> s >> t;
		a.pb(P(s, i));
		b.pb(P(t, i));
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), greater<P>());
	rep(i, n-1){
		if(a[i].second == b[i].second){
			if(a[i].first >= b[i].first || i == 0){
				P tmp = b[i];
				b[i] = b[i+1];
				b[i+1] = tmp;
			}
		}
	}
	rrep(i, n-1){
		if(a[i+1].second == b[i+1].second){
			if(a[i+1].first < b[i+1].first || i == n-2){
				P tmp = b[i+1];
				b[i+1] = b[i];
				b[i] = tmp;
			}
		}
	}
	ll ans = 0;
	rep(i, n){
		ans += min(a[i].first, b[i].first);
	}
	cout << ans << END;
}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	solve();
	return 0;
}

Submission Info

Submission Time
Task C - Min Cost Cycle
User niimi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1245 Byte
Status
Exec Time 37 ms
Memory 2036 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 0 / 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 1 ms 256 KB
sample-02.txt 1 ms 256 KB
sample-03.txt 1 ms 256 KB
subtask01-01.txt 1 ms 256 KB
subtask01-02.txt 26 ms 2036 KB
subtask01-03.txt 35 ms 2036 KB
subtask01-04.txt 1 ms 256 KB
subtask01-05.txt 23 ms 1524 KB
subtask01-06.txt 25 ms 2036 KB
subtask01-07.txt 34 ms 2036 KB
subtask01-08.txt 32 ms 2036 KB
subtask01-09.txt 23 ms 1396 KB
subtask01-10.txt 24 ms 1524 KB
subtask01-11.txt 30 ms 2036 KB
subtask01-12.txt 32 ms 2036 KB
subtask01-13.txt 18 ms 1276 KB
subtask01-14.txt 36 ms 2036 KB
subtask01-15.txt 37 ms 2036 KB
subtask01-16.txt 36 ms 2036 KB
subtask01-17.txt 36 ms 2036 KB
subtask01-18.txt 36 ms 2036 KB
subtask01-19.txt 36 ms 2036 KB
subtask01-20.txt 36 ms 2036 KB
subtask01-21.txt 37 ms 2036 KB
subtask01-22.txt 37 ms 2036 KB
subtask01-23.txt 37 ms 2036 KB
subtask01-24.txt 36 ms 2036 KB
subtask01-25.txt 36 ms 2036 KB