Submission #720741

#TimeUsernameProblemLanguageResultExecution timeMemory
720741mseebacherPalembang Bridges (APIO15_bridge)C++17
9 / 100
2071 ms340 KiB
#include <bits/stdc++.h> using namespace std; // Idee 1 -> Set mit Wert|Index pair // Idee 2 -> SegTree damit struct Platz{ char type; int c; }; void solve(){ int k; cin >> k; int n; cin >> n; vector<Platz> home(n); vector<Platz> arbeit(n); set<int> coords; for(int i = 0;i<n;i++){ cin >> home[i].type >> home[i].c >> arbeit[i].type >> arbeit[i].c; coords.insert(home[i].c); coords.insert(arbeit[i].c); } long long ans = 1e18; for(set<int>::iterator it = coords.begin();it!=coords.end();it++){ for(set<int>::iterator it2 = it;it2 !=coords.end();it2++){ long long sum = 0; for(int j = 0;j<n;j++){ if(home[j].type == arbeit[j].type){ sum += abs(home[j].c-arbeit[j].c); }else{ sum += min(abs(home[j].c-*it)+abs(arbeit[j].c - *it), abs(home[j].c-*it2) + abs(arbeit[j].c - *it2))+1; } } ans = min(ans,sum); } } cout << ans; } int main(){ ios::sync_with_stdio(0); cin.tie(nullptr); cout << fixed << setprecision(8); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...