Submission #922178

#	Time	Username	Problem	Language	Result	Execution time	Memory
922178		Aiperiii	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	155 ms	20176 KiB

bridge

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int k,n;
   cin>>k>>n;
   vector <char> t1(n),t2(n);
   vector <int> x(n),y(n);
   int ans=0;
   vector <vector <int> > v;
   for(int i=0;i<n;i++){
      cin>>t1[i]>>x[i]>>t2[i]>>y[i];
      if(t1[i]==t2[i]){
         ans+=abs(x[i]-y[i]);
      }
      else{
         v.pb({x[i]+y[i],x[i],y[i]});
         ans++;
      }
   }
   sort(all(v));
   multiset <int> l,r;
   vector <int> pr;
   int suml=0,sumr=0;
   for(int i=0;i<v.size();i++){
      if(l.size()!=0 && *l.rbegin()>v[i][1]){
         l.insert(v[i][1]);
         suml+=v[i][1];
      }
      else{
         r.insert(v[i][1]);
         sumr+=v[i][1];
      }
      if(l.size()!=0 && *l.rbegin()>v[i][2]){
         l.insert(v[i][2]);
         suml+=v[i][2];
      }
      else{
         r.insert(v[i][2]);
         sumr+=v[i][2];
      }
      while(r.size()>l.size()){
         int cur=*r.begin();
         r.erase(r.begin());
         sumr-=cur;
         l.insert(cur);
         suml+=cur;
      }
      while(l.size()>r.size()+1){
         int cur=*l.rbegin();
         auto it=l.end();it--;
         l.erase(it);
         suml-=cur;
         r.insert(cur);
         sumr+=cur;
      }
      int med=*l.rbegin();
      int x=l.size(),y=r.size();
      pr.pb((med*x-suml)+(sumr-y*med));
   }
   if(k==1){
      if(pr.size()!=0)ans+=pr.back();
      cout<<ans<<"\n";return 0;
   }
   l.clear();r.clear();
   suml=0;sumr=0;
   int mn=1e18;
   for(int i=v.size()-1;i>=0;i--){
      if(l.size()!=0 && *l.rbegin()>v[i][1]){
         l.insert(v[i][1]);
         suml+=v[i][1];
      }
      else{
         r.insert(v[i][1]);
         sumr+=v[i][1];
      }
      if(l.size()!=0 && *l.rbegin()>v[i][2]){
         l.insert(v[i][2]);
         suml+=v[i][2];
      }
      else{
         r.insert(v[i][2]);
         sumr+=v[i][2];
      }
      while(r.size()>l.size()){
         int cur=*r.begin();
         r.erase(r.begin());
         sumr-=cur;
         l.insert(cur);
         suml+=cur;
      }
      while(l.size()>r.size()+1){
         int cur=*l.rbegin();
         auto it=l.end();it--;
         l.erase(it);
         suml-=cur;
         r.insert(cur);
         sumr+=cur;
      }
      int med=*l.rbegin();
      int x=l.size(),y=r.size();
      int sf=(med*x-suml)+(sumr-y*med);
      if(i-1>=0)sf+=pr[i-1];
      mn=min(mn,sf);
   }
   cout<<mn+ans<<"\n";
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:31:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i=0;i<v.size();i++){
      |                ~^~~~~~~~~

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