제출 #1212501

#제출 시각아이디문제언어결과실행 시간메모리
1212501loomPalembang Bridges (APIO15_bridge)C++20
0 / 100
0 ms320 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define inf 5e18 #define nl '\n' bool cmp(pair<int,int> p1, pair<int,int> p2){ return p1.first+p1.second < p2.first+p2.second; } vector<pair<int,int>> v; int n; vector<int> func(){ vector<int> lc(n); priority_queue<int> lo; priority_queue<int, vector<int>, greater<int>> hi; int ls = 0, rs = 0; for(int i=0; i<n; i++){ auto [l, r] = v[i]; if(lo.empty() or l <= lo.top()) lo.push(l), ls += l; else hi.push(l), rs += l; if(lo.empty() or r <= lo.top()) lo.push(r), ls += r; else hi.push(r), rs += r; if(lo.size() > hi.size()){ int x = lo.top(); hi.push(x), rs += x; lo.pop(), ls -= x; } else if(hi.size() > lo.size()){ int x = hi.top(); lo.push(x), ls += x; hi.pop(), rs -= x; } int m = lo.top(); lc[i] = rs - ls; } return lc; } inline void solve(){ int k; cin>>k>>n; int ini = 0; for(int i=0; i<n; i++){ char p, q; int a, b; cin>>p>>a>>q>>b; if(p == q) ini += abs(a-b); else ini++, v.push_back({min(a, b), max(a, b)}); } n = v.size(); sort(v.begin(), v.end()); auto lc = func(); reverse(v.begin(), v.end()); auto rc = func(); int mn = min(lc[n-1], rc[n-1]); for(int i=0; i<n-1; i++){ mn = min(mn, lc[i] + rc[n-i-2]); } cout<<ini + (k == 1 ? lc[n-1] : mn); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); 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...