Contest Duration: ~ (local time) (150 minutes) Back to Home

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 2018-10-13 23:08:56+0900 C - Min Cost Cycle niimi C++14 (GCC 5.4.1) 0 1245 Byte WA 37 ms 2036 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
 AC × 3
 AC × 19 WA × 12
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.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