Submission #961871

#	Time	Username	Problem	Language	Result	Execution time	Memory
961871		vjudge1	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	266 ms	13512 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

#define int long long

int k, n;

namespace sub12{
   void solve(){
      vector<int> v;
      int ans=0;
      for (int i=1; i<=n; ++i){
         char c1, c2; int p1, p2;
         cin >> c1 >> p1 >> c2 >> p2;
         if (c1==c2) ans+=abs(p1-p2);
         else v.push_back(p1), v.push_back(p2);
      }
      sort(v.begin(), v.end());
      if (v.size()){
         int pos=v[(int)v.size()/2];
         for (int i:v) ans+=abs(pos-i);
      }
      cout << ans+(int)v.size()/2 << '\n';
   }
}

struct Median{
   multiset<int, greater<int>> stl;
   int suml;
   multiset<int> str;
   int sumr;
   void adjust(){
      while ((int)stl.size()-(int)str.size()>1){
         int tmp=*stl.begin();
         str.insert(tmp); sumr+=tmp;
         stl.erase(stl.begin()); suml-=tmp;
      }
      while ((int)str.size()-(int)stl.size()>0){
         int tmp=*str.begin();
         stl.insert(tmp); suml+=tmp;
         str.erase(str.begin()); sumr-=tmp;
      }
   }
   void insert(int x){
      if (stl.empty() || *stl.begin()>=x) stl.insert(x), suml+=x;
      else str.insert(x), sumr+=x;
      adjust();
   }
   void erase(int x){
      if (stl.find(x)!=stl.end()) stl.erase(stl.find(x)), suml-=x;
      else str.erase(str.find(x)), sumr-=x;
      adjust();
   }
   int calc(){
      if (stl.empty()) return 0;
      int median=*stl.begin();
      return sumr-median*((int)str.size())+median*((int)stl.size())-suml;
   }
};

namespace sub345{
   Median st1, st2;
   void solve(){
      int add=0;
      vector<pair<int, int>> v;
      for (int i=1; i<=n; ++i){
         char c1, c2; int p1, p2;
         cin >> c1 >> p1 >> c2 >> p2;
         if (c1==c2) add+=abs(p1-p2);
         else v.emplace_back(p1, p2);
      }
      sort(v.begin(), v.end(), [&](pair<int, int> x, pair<int, int> y){
         return x.first+x.second<y.first+y.second;
      }); 
      int ans=1e18;
      for (auto &i:v) st2.insert(i.first), st2.insert(i.second);
      for (int i=0; i<=(int)v.size(); ++i){
         ans=min(ans, st1.calc()+st2.calc());
         if (i<(int)v.size()){
            st2.erase(v[i].first);
            st2.erase(v[i].second);
            st1.insert(v[i].first);
            st1.insert(v[i].second);
         }
      }
      cout << add+ans+(int)v.size() << '\n';
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> k >> n;
   if (k==1) sub12::solve();
   else sub345::solve();
   return 0;
}

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