# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25018 | 2017-06-20T04:15:43 Z | 윤교준(#1055) | Palembang Bridges (APIO15_bridge) | C++11 | 73 ms | 6380 KB |
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <deque> #include <queue> #include <set> #include <map> #include <unordered_map> #include <bitset> #include <string> #define pb push_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define befv(V) ((V)[(sz(V)-2)]) #define sorv(V) sort(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define upmin(a,b) (a)=min((a),(b)) #define upmax(a,b) (a)=max((a),(b)) #define INF (1100000099) #define INFLL (1100000000000000099ll) #define MAXN (100005) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<int, ll> pil; typedef pair<ll, int> pli; inline ll myabs(const ll& n) { return n < 0 ? -n : n; } ll d[2][MAXN]; int A[MAXN], B[MAXN], P[MAXN]; int N, K; ll Ans; void input() { scanf("%d%d", &K, &N); int cnt = 0; for(int i = 0; i < N; i++) { int x, y; char a, b; scanf(" %c%d %c%d", &a, &x, &b, &y); if(a == b) { Ans += myabs(x-y); continue; } A[cnt] = x; B[cnt] = y; cnt++; } N = cnt; } void process1() { vector<int> V; for(int i = 0; i < N; i++) { V.pb(A[i]); V.pb(B[i]); } sorv(V); const int X = V[sz(V)/2]; for(int i = 0; i < N; i++) Ans += myabs((ll)A[i] - X) + myabs((ll)B[i] - X); Ans += sz(V)/2; } multiset<int> Q; void meanF(ll d[]) { multiset<int>().swap(Q); Q.insert(A[P[0]]); Q.insert(B[P[0]]); auto it = Q.begin(); d[0] = myabs((ll)A[P[0]] - (*it)) + myabs((ll)B[P[0]] - (*it)); for(int p_i = 1; p_i < N; p_i++) { const int &idx = P[p_i]; ll &ret = d[p_i]; if(A[idx] > B[idx]) swap(A[idx], B[idx]); if(B[idx] <= (*it)) { const int prv = *it; Q.insert(A[idx]); Q.insert(B[idx]); it--; ret = d[p_i-1] + (ll)(*it)*2 - A[idx] - B[idx] + ((ll)prv-(*it))*2; } else if((*it) <= A[idx]) { Q.insert(A[idx]); Q.insert(B[idx]); it++; ret = d[p_i-1] + A[idx] + B[idx] - (ll)(*it)*2; } else { Q.insert(A[idx]); Q.insert(B[idx]); ret = d[p_i-1] + B[idx] - A[idx]; } } } void process2() { for(int i = 0; i < N; i++) P[i] = i; sort(P, P+N, [&](const int& a, const int& b) -> bool { return (A[a]+B[a]) < (A[b]+B[b]); }); meanF(d[0]); reverse(P, P+N); meanF(d[1]); reverse(d[1], d[1]+N); reverse(P, P+N); ll ret = d[0][0] + d[1][1]; for(int i = 0; i+1 < N; i++) { upmin(ret, d[0][i] + d[1][i+1]); } Ans += ret + N; } int main() { input(); if(!N); else if(1 == N) { Ans += myabs(A[0] - B[0]); } else if(1 == K) process1(); else process2(); printf("%lld\n", Ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4760 KB | Output is correct |
2 | Correct | 0 ms | 4760 KB | Output is correct |
3 | Correct | 0 ms | 4760 KB | Output is correct |
4 | Correct | 0 ms | 4760 KB | Output is correct |
5 | Correct | 0 ms | 4760 KB | Output is correct |
6 | Correct | 0 ms | 4760 KB | Output is correct |
7 | Correct | 0 ms | 4760 KB | Output is correct |
8 | Correct | 0 ms | 4760 KB | Output is correct |
9 | Correct | 0 ms | 4760 KB | Output is correct |
10 | Correct | 0 ms | 4760 KB | Output is correct |
11 | Correct | 0 ms | 4760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4760 KB | Output is correct |
2 | Correct | 0 ms | 4760 KB | Output is correct |
3 | Correct | 0 ms | 4760 KB | Output is correct |
4 | Correct | 0 ms | 4760 KB | Output is correct |
5 | Correct | 0 ms | 4760 KB | Output is correct |
6 | Correct | 0 ms | 4760 KB | Output is correct |
7 | Correct | 0 ms | 4760 KB | Output is correct |
8 | Correct | 0 ms | 4760 KB | Output is correct |
9 | Correct | 0 ms | 4760 KB | Output is correct |
10 | Correct | 0 ms | 4760 KB | Output is correct |
11 | Correct | 0 ms | 4760 KB | Output is correct |
12 | Correct | 33 ms | 6380 KB | Output is correct |
13 | Correct | 73 ms | 6380 KB | Output is correct |
14 | Correct | 63 ms | 6380 KB | Output is correct |
15 | Correct | 53 ms | 5612 KB | Output is correct |
16 | Correct | 33 ms | 6380 KB | Output is correct |
17 | Correct | 46 ms | 6380 KB | Output is correct |
18 | Correct | 56 ms | 6380 KB | Output is correct |
19 | Correct | 63 ms | 6380 KB | Output is correct |
20 | Correct | 46 ms | 6380 KB | Output is correct |
21 | Correct | 69 ms | 6380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4760 KB | Output is correct |
2 | Correct | 0 ms | 4760 KB | Output is correct |
3 | Incorrect | 0 ms | 4760 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4760 KB | Output is correct |
2 | Correct | 0 ms | 4760 KB | Output is correct |
3 | Incorrect | 0 ms | 4760 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4760 KB | Output is correct |
2 | Correct | 0 ms | 4760 KB | Output is correct |
3 | Incorrect | 0 ms | 4760 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |