# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
914652 | 2024-01-22T13:22:58 Z | 12345678 | Palembang Bridges (APIO15_bridge) | C++17 | 1 ms | 1116 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<<res<<' '<<l[i]<<' '<<l[j]<<' '<<cal(l[i], l[j])<<'\n'; } cout<<ans; } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */
Compilation message
# | 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 | - |
# | 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 | 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 | - |