Submission #1016929

#TimeUsernameProblemLanguageResultExecution timeMemory
1016929TroySerPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; const long long int INF = 1e18; long long int K, N; long long int build1, build2; char zone1, zone2; long long int Dmin = 0; struct Place { char zone; long long int building; }; vector<pair<Place, Place> > people; int M; bool cmp(const pair<Place, Place> &a, const pair<Place, Place> &b) { return a.first.building < b.first.building; } bool cmp2(const pair<Place, Place> &a, const pair<Place, Place> &b) { return a.second.building < b.second.building; } int main() { cin >> K >> N; for (int i = 0; i < N; i++) { cin >> zone1 >> build1 >> zone2 >> build2; if (zone1 == zone2) { Dmin += abs(build2 - build1); } else { people.push_back(make_pair( (Place){zone1, build1}, (Place){zone2, build2} )); } } M = people.size(); long long int possibleMin = INF; if (M == 0) { possibleMin = 0; } else { sort(people.begin(), people.end(), cmp); for (int i = M/2; i <= M/2 + 1; i++) { long long int currK = people[i].first.building; long long int currMin = 0; for (int j = 0; j < M; j++) { currMin += abs(people[j].first.building - currK); currMin++; currMin += abs(people[j].second.building - currK); } possibleMin = min(currMin, possibleMin); currK = people[i].second.building; currMin = 0; for (int j = 0; j < M; j++) { currMin += abs(people[j].first.building - currK); currMin++; currMin += abs(people[j].second.building - currK); } possibleMin = min(currMin, possibleMin); } sort(people.begin(), people.end(), cmp2); for (int i = M/2; i <= M/2 + 1; i++) { long long int currK = people[i].first.building; long long int currMin = 0; for (int j = 0; j < M; j++) { currMin += abs(people[j].first.building - currK); currMin++; currMin += abs(people[j].second.building - currK); } possibleMin = min(currMin, possibleMin); currK = people[i].second.building; currMin = 0; for (int j = 0; j < M; j++) { currMin += abs(people[j].first.building - currK); currMin++; currMin += abs(people[j].second.building - currK); } possibleMin = min(currMin, possibleMin); } } cout << possibleMin + Dmin << "\n"; }
#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...