Submission #1054355

#TimeUsernameProblemLanguageResultExecution timeMemory
1054355HaroldPalembang Bridges (APIO15_bridge)C++14
22 / 100
25 ms3272 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long int main() { ios_base::sync_with_stdio(0); cin.tie(0); /*int k, n; cin >> k >> n; vector<pair<int, int>> a, p; int res = 0; for(int i = 0; i < n; i++) { char c1, c2; int a1, a2; cin >> c1 >> a1 >> c2 >> a2; if(c1 == c2) { res += abs(a1-a2); } else { a.push_back({a1, a2}); } } // incorrect when k = 2 couse need to choose sort(a.begin(), a.end()); for(auto i: a) { pair<int, int> cur = {i.first, i.second}; if(p.empty()) { p.push_back(cur); continue; } if(p.back().second >= cur.first) { p.back() = {cur.first, p.back().second}; } else { p.push_back(cur); } } int i = 0; // point to cur element in a int j = 0; // point to element in p int cross = 0; while(k > 0 && j < p.size()) { cross = p[j].second; while(i < a.size() && a[i].first <= cross) { res += abs(a[i].second-a[i].first); i++; } j++; k--; } while(i < a.size()) { res += abs(a[i].second-a[i].first) + 2*abs(cross-a[i].first); i++; } cout << res+a.size() << endl;*/ int k, n; cin >> k >> n; vector<int> a; vector<pair<ll, ll>> p; ll res = 0; for(int i = 0; i < n; i++) { char c1, c2; ll a1, a2; cin >> c1 >> a1 >> c2 >> a2; if(c1 == c2) { res += abs(a1-a2); } else { a.push_back(a1); a.push_back(a2); p.push_back({a1, a2}); } } sort(a.begin(), a.end()); if(k == 1) { int m = a.size()/2; for(auto i: p) { res += abs(a[m]-i.first) + abs(a[m]-i.second)+1; } } else { // dist from middle should be as small as possible ll l = 0, r = 0; for(int i = 0; i < n; i++) { r += a[i]; } ll cur = r; for(int i = 0; i < n; i++) { r -= a[i]; l += a[i]; cur = min(cur, r-l); } res += cur; } cout << res << "\n"; return 0; }
#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...