oj.uz

답안 #922166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922166 2024-02-05T07:53:05 Z Aiperiii Palembang Bridges (APIO15_bridge) C++14
0 / 100
 1 ms 436 KB 
#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();
         l.erase(--l.end());
         suml-=cur;
         r.insert(cur);
         sumr+=cur;
      }
      int med=*l.rbegin();
      pr.pb((med*l.size()-suml)+(sumr-r.size()*med));
   }
   if(k==1){
      cout<<ans+pr.back()<<"\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();
         l.erase(--l.end());
         suml-=cur;
         r.insert(cur);
         sumr+=cur;
      }
      int med=*l.rbegin();
      int sf=(med*l.size()-suml)+(sumr-r.size()*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

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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -