Submission #1077275

#TimeUsernameProblemLanguageResultExecution timeMemory
1077275MuhammetPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sz(x) (int)x.size() #define ff first #define ss second const int N = 300005; const int M = 1e9 + 7; int T, n, k, s1[N], s2[N]; char c1[N], c2[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> k >> n; for(int i = 1; i <= n; i++){ cin >> c1[i] >> s1[i] >> c2[i] >> s2[i]; } int ans = 0; if(k == 1){ vector <int> v; for(int i = 1; i <= n; i++){ if(c1[i] == c2[i]){ ans += abs(s1[i]-s2[i]); } else { v.push_back(s1[i]); v.push_back(s2[i]); } } sort(v.begin(), v.end()); int x = (sz(v)+1)/2; x--; if(x >= 0) x = v[x]; for(auto i : v){ ans += abs(i-x); } cout << ans+sz(v)/2 << "\n"; return 0; } vector <pair<int,pair<int,int>>> v1; for(int i = 1; i <= n; i++){ if(c1[i] != c2[i]){ v1.push_back({(s1[i]+s2[i]/2),{min(s1[i],s2[i]),max(s1[i],s2[i])}}); } else { ans += abs(s1[i]-s2[i]); } } ans += sz(v1); if(sz(v1) > 0){ sort(v1.begin(), v1.end()); } multiset <int> st1, st2; vector <int> p(sz(v1),0), f(sz(v1),0); for(int j = 0; j < sz(v1); j++){ pair <int,pair<int,int>> i = v1[j]; st1.insert(i.ss.ff); st1.insert(i.ss.ss); st2.insert(*st1.rbegin()); st1.erase(--st1.end()); st2.insert(*st1.rbegin()); st1.erase(--st1.end()); st1.insert(*st2.begin()); st2.erase(st2.begin()); int med = (*st1.rbegin()); for(int j1 = 0; j1 <= j; j1++){ p[j] += abs(med-v1[j1].ss.ff); p[j] += abs(med-v1[j1].ss.ss); } } for(int j = sz(v1)-1; j >= 0; j--){ pair <int,pair<int,int>> i = v1[j]; st1.insert(i.ss.ff); st1.insert(i.ss.ss); st2.insert(*st1.rbegin()); st1.erase(--st1.end()); st2.insert(*st1.rbegin()); st1.erase(--st1.end()); st1.insert(*st2.begin()); st2.erase(st2.begin()); int med = (*st1.rbegin()); for(int j1 = sz(v1)-1; j1 >= j; j1--){ f[j] += abs(med-v1[j1].ss.ff); f[j] += abs(med-v1[j1].ss.ss); } } int mn = min(p[sz(v1)-1],f[0]); for(int i = 0; i < sz(v1)-1; i++){ mn = min(mn,p[i]+f[i+1]); } cout << ans + mn << "\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...