# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25036 | 2017-06-20T04:47:08 Z | 김동현(#1052) | Palembang Bridges (APIO15_bridge) | C++14 | 99 ms | 3648 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Lin{ int s, e; bool operator<(const Lin &oth) const { return s + e < oth.s + oth.e; } }; const ll inf = 1e18; int k, n; vector<int> v; vector<ll> w; vector<Lin> u; ll ans, cans, bs; void t1(){ scanf("%d", &n); for(int i = 1, x, y; i <= n; i++){ char a[3], b[3]; scanf("%s%d%s%d", a, &x, b, &y); if(a[0] == b[0]) ans += abs(x - y); else{ v.push_back(x); v.push_back(y); ans++; } } sort(v.begin(), v.end()); for(auto &i : v) ans += abs(i - v[v.size() / 2]); printf("%lld\n", ans); } void t2(){ scanf("%d", &n); for(int i = 1, x, y; i <= n; i++){ char a[3], b[3]; scanf("%s%d%s%d", a, &x, b, &y); if(a[0] == b[0]) bs += abs(x - y); else{ u.push_back({x, y}); bs++; } } sort(u.begin(), u.end()); ans = inf; for(int i = 0; i < u.size(); i++){ cans = 0; ll cm = u[i].s + u[i].e; for(int j = 0; j < i; j++){ w.push_back(cm - 2LL * u[i].s); w.push_back(cm - 2LL * u[i].e); } for(int j = i; j < u.size(); j++){ w.push_back(2LL * u[i].s - cm); w.push_back(2LL * u[i].e - cm); } sort(w.begin(), w.end()); for(auto &j : w) cans += abs(j - w[w.size() / 2]); ans = min(ans, cans / 2); } printf("%lld\n", ans + bs); } int main(){ scanf("%d", &k); if(k == 1) t1(); else t2(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2028 KB | Output is correct |
2 | Correct | 0 ms | 2028 KB | Output is correct |
3 | Correct | 0 ms | 2028 KB | Output is correct |
4 | Correct | 0 ms | 2028 KB | Output is correct |
5 | Correct | 0 ms | 2028 KB | Output is correct |
6 | Correct | 0 ms | 2028 KB | Output is correct |
7 | Correct | 0 ms | 2028 KB | Output is correct |
8 | Correct | 0 ms | 2028 KB | Output is correct |
9 | Correct | 0 ms | 2028 KB | Output is correct |
10 | Correct | 0 ms | 2028 KB | Output is correct |
11 | Correct | 0 ms | 2028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2028 KB | Output is correct |
2 | Correct | 0 ms | 2028 KB | Output is correct |
3 | Correct | 0 ms | 2028 KB | Output is correct |
4 | Correct | 0 ms | 2028 KB | Output is correct |
5 | Correct | 0 ms | 2028 KB | Output is correct |
6 | Correct | 0 ms | 2028 KB | Output is correct |
7 | Correct | 0 ms | 2028 KB | Output is correct |
8 | Correct | 0 ms | 2028 KB | Output is correct |
9 | Correct | 0 ms | 2028 KB | Output is correct |
10 | Correct | 0 ms | 2028 KB | Output is correct |
11 | Correct | 0 ms | 2028 KB | Output is correct |
12 | Correct | 43 ms | 3648 KB | Output is correct |
13 | Correct | 99 ms | 3648 KB | Output is correct |
14 | Correct | 49 ms | 3648 KB | Output is correct |
15 | Correct | 33 ms | 2880 KB | Output is correct |
16 | Correct | 36 ms | 3648 KB | Output is correct |
17 | Correct | 66 ms | 3648 KB | Output is correct |
18 | Correct | 49 ms | 3648 KB | Output is correct |
19 | Correct | 66 ms | 3648 KB | Output is correct |
20 | Correct | 39 ms | 3648 KB | Output is correct |
21 | Correct | 56 ms | 3648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 2028 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 2028 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 2028 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |