Submission #1212501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212501		loom	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	320 KiB

bridge

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37