# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
914653 | 2024-01-22T13:23:37 Z | 12345678 | Palembang Bridges (APIO15_bridge) | C++17 | 33 ms | 4312 KB |
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5; #define ll long long int k, n, b, d, cnt; char a, c; vector<int> v, l; vector<pair<int, int>> p(nx); long long res, ans=LLONG_MAX; ll cal(int b1, int b2) { ll tmp=0; for (int i=0; i<cnt; i++) tmp+=min(abs(p[i].first-b1)+abs(p[i].second-b1), abs(p[i].first-b2)+abs(p[i].second-b2))+1; //cout<<"here "<<p[i].first<<' '<<p[i].second<<' '<<tmp<<'\n'; return tmp; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>k>>n; if (k==1) { for (int i=0; i<n; i++) { cin>>a>>b>>c>>d; if (a==c) { res+=abs(b-d); continue; } v.push_back(b); v.push_back(d); res++; } sort(v.begin(), v.end()); int md=v[v.size()/2]; for (auto x:v) res+=abs(x-md); cout<<res; } else { for (int i=0; i<n; i++) { cin>>a>>b>>c>>d; if (a==c) res+=abs(b-d); else p[cnt++]={b, d}, l.push_back(b), l.push_back(d); } for (int i=0; i<l.size(); i++) for (int j=i; j<l.size(); j++) ans=min(ans, res+cal(l[i], l[j])); cout<<ans; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1112 KB | Output is correct |
2 | Correct | 1 ms | 1116 KB | Output is correct |
3 | Correct | 1 ms | 1116 KB | Output is correct |
4 | Correct | 1 ms | 1116 KB | Output is correct |
5 | Correct | 1 ms | 1116 KB | Output is correct |
6 | Correct | 1 ms | 1272 KB | Output is correct |
7 | Correct | 1 ms | 1112 KB | Output is correct |
8 | Correct | 1 ms | 1116 KB | Output is correct |
9 | Correct | 1 ms | 1116 KB | Output is correct |
10 | Correct | 1 ms | 1116 KB | Output is correct |
11 | Correct | 1 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1116 KB | Output is correct |
2 | Correct | 1 ms | 1116 KB | Output is correct |
3 | Correct | 1 ms | 1116 KB | Output is correct |
4 | Correct | 1 ms | 1116 KB | Output is correct |
5 | Correct | 1 ms | 1116 KB | Output is correct |
6 | Correct | 1 ms | 1116 KB | Output is correct |
7 | Correct | 1 ms | 1112 KB | Output is correct |
8 | Correct | 1 ms | 1116 KB | Output is correct |
9 | Correct | 1 ms | 1116 KB | Output is correct |
10 | Correct | 1 ms | 1264 KB | Output is correct |
11 | Correct | 1 ms | 1056 KB | Output is correct |
12 | Correct | 16 ms | 3032 KB | Output is correct |
13 | Correct | 33 ms | 4312 KB | Output is correct |
14 | Correct | 24 ms | 3548 KB | Output is correct |
15 | Correct | 19 ms | 3036 KB | Output is correct |
16 | Correct | 19 ms | 3800 KB | Output is correct |
17 | Correct | 22 ms | 4308 KB | Output is correct |
18 | Correct | 27 ms | 4056 KB | Output is correct |
19 | Correct | 31 ms | 4300 KB | Output is correct |
20 | Correct | 22 ms | 4056 KB | Output is correct |
21 | Correct | 29 ms | 4056 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 1112 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 1116 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 1116 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |